BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-84-1003
       ENTRY:: May 29, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Parallelism and greedy algorithms
        TYPE:: Technical Report
      AUTHOR:: Anderson, Richard
      AUTHOR:: Mayr, Ernst
        DATE:: April 1984
       PAGES:: 18
    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.
       NOTES:: [Adminitrivia V1/Prg/19950529]
         END:: STAN//CS-TR-84-1003