Polynomial complete scheduling problems
Jeffrey David Ullman ยท 1973
We show that the problem of finding an optimal schedule for a set of jobs is polynomial complete even in the following two restricted cases.
Cited by 83 works. doi:10.1145/800009.808055
Authors
References
- The Design and Analysis of Computer Algorithms
- Reducibility among Combinatorial Problems
- The complexity of theorem-proving procedures
- Optimal scheduling for two-processor systems
- Optimal Sequencing of Two Equivalent Processors
- Some related problems from network flows, game theory and integer programming
- Complete register allocation problems
- Bounds on multiprocessing anomalies and packing algorithms
- Reducibility among Combinatorial Problems (1972)