BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-85-1079
       ENTRY:: May 01, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Two processor scheduling is in NC
        TYPE:: Technical Report
      AUTHOR:: Helmbold, David
      AUTHOR:: Mayr, Ernst
        DATE:: October 1985
       PAGES:: 22
    ABSTRACT:: We present a parallel algorithm for the two processor
               scheduling problem. This algorithm constructs an optimal
               schedule for unit execution time task systems with arbitrary
               precedence constraints using a polynomial number of
               processors and running in time polylog in the size of the
               input. Whereas previous parallel solutions for the problem
               made extensive use of randomization, our algorithm is
               completely deterministic and based on an interesting
               decomposition technique. And it is of independent relevance
               for two more reasons. It provides another example for the
               apparent difference in complexity between decision and search
               problems in the context of fast parallel computation, and it
               gives an NC-algorithm for the matching problem in certain
               restricted cases.
       NOTES:: [Adminitrivia V1/Prg/19950501]
         END:: STAN//CS-TR-85-1079