Report Number: CS-TR-85-1079
Institution: Stanford University, Department of Computer Science
Title: Two processor scheduling is in NC
Author: Helmbold, David
Author: Mayr, Ernst
Date: October 1985
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.
http://i.stanford.edu/pub/cstr/reports/cs/tr/85/1079/CS-TR-85-1079.pdf