Two Processor Scheduling is in $\mathcal{NC}$
- 1 August 1987
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 16 (4) , 747-759
- https://doi.org/10.1137/0216050
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.Keywords
This publication has 8 references indexed in Scilit:
- NC algorithms for comparability graphs, interval graphs, and testing for unique perfect matchingPublished by Springer Nature ,1985
- An Almost-Linear Algorithm for Two-Processor SchedulingJournal of the ACM, 1982
- Scheduling Interval-Ordered TasksSIAM Journal on Computing, 1979
- NP-complete scheduling problemsJournal of Computer and System Sciences, 1975
- Optimal scheduling for two-processor systemsActa Informatica, 1972
- Transitive Orientation of Graphs and Identification of Permutation GraphsCanadian Journal of Mathematics, 1971
- Optimal Sequencing of Two Equivalent ProcessorsSIAM Journal on Applied Mathematics, 1969
- Parallel Sequencing and Assembly Line ProblemsOperations Research, 1961