Path: utzoo!attcan!uunet!ncrlnk!ncrcae!hubcap!Matthew
From: mcvax!ivax.doc.imperial.ac.uk!mmh@uunet.uu.net (Matthew Huntbach)
Newsgroups: comp.parallel
Subject: Re: Superlinear
Message-ID: <3857@hubcap.UUCP>
Date: 13 Dec 88 14:40:26 GMT
Sender: fpst@hubcap.UUCP
Lines: 10
Approved: parallel@hubcap.clemson.edu

What I was assuming was that you have an algorithm where the any solution
is acceptable and on the whole a depth-first search leads to solutions quickest.
It just happens that in this particular example, the heuristics lead you down
the wrong path. I assumed the two processors still searched depth-first, so a
completely breadth-first search would not give a quicker solution.

I agree that bringing in parallelism could be said to have altered the algorithm
by introducing some breadth-first search into what was a purely depth-first
search. But this is what is generally accepted by the term "superlinear 
speedup"