Report Number: CS-TR-84-1003
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