@inproceedings{9d6b9053d6bc4858a2003d3ac20436cf,
title = "Two processor scheduling is in NC",
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 iteration technique. 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.",
author = "David Helmbold and Ernst Mayr",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1986.; Aegean Workshop on Computing: VLSI Algorithms and Architectures, AWOC 1986 ; Conference date: 08-07-1986 Through 11-07-1986",
year = "1986",
doi = "10.1007/3-540-16766-8_2",
language = "English",
isbn = "9783540167662",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "12--25",
editor = "Kurt Mehlhorn and Fillia Makedon and T. Papatheodorou and P. Spirakis",
booktitle = "VLSl Algorithms and Architectures - Aegean Workshop on Computing, Proceedings",
}