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