valoisj@turing.cs.rpi.edu (John Valois) (02/09/90)
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