Institution: Stanford University, Department of Computer Science

Title: Parallelism and greedy algorithms

Author: Anderson, Richard

Author: Mayr, Ernst

Date: April 1984

Abstract: A number of greedy algorithms are examined and are shown to be probably inherently sequential. Greedy algorithms are presented for finding a maximal path, for finding a maximal set of disjoint paths in a layered dag, and for finding the largest induced subgraph of a graph that has all vertices of degree at least k. It is shown that for all of these algorithms, the problem of determining if a given node is in the solution set of the algorithm is P-complete. This means that it is unlikely that these sequential algorithms can be sped up significantly using parallelism.

http://i.stanford.edu/pub/cstr/reports/cs/tr/84/1003/CS-TR-84-1003.pdf