Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!usc!ucsd!ucsdhub!hp-sdd!ncr-sd!ncrcae!hubcap!valoisj
From: valoisj@turing.cs.rpi.edu (John Valois)
Newsgroups: comp.parallel
Subject: Non-optimal parallel algorithms
Message-ID: <7930@hubcap.clemson.edu>
Date: 9 Feb 90 13:13:37 GMT
Sender: fpst@hubcap.clemson.edu
Lines: 13
Approved: parallel@hubcap.clemson.edu

I am looking for references to problems for which the best known
parallel algorithms are not optimal; i.e. the work (processor-time
product) done by the parallel algorithm is greater than the running
time of a sequential algorithm.

Three problems I know of are integer sorting, maximal independent set,
and unweighted single source shortest paths. I am especially
interested in problems for which the parallel and sequential work
differ by more than a log factor.

Replies by e-mail, please.

John Valois