×
Ullman, J. D.

NP-complete scheduling problems. (English) Zbl 0313.68054

J. Comput. Syst. Sci. 10, 384-393 (1975).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0313.68054

Cited in 2 Reviews
Cited in 118 Documents

MSC:

68Q45 Formal languages and automata
03D10 Turing machines and related notions
PDFBibTeX XMLCite
\textit{J. D. Ullman}, J. Comput. Syst. Sci. 10, 384--393 (1975; Zbl 0313.68054)
Full Text: DOI

References:

[1] Graham, R. L., Bounds on multiprocessing anomalies and packing algorithms, (Proc. SJCC (1972)), 205-218
[2] Cook, S. A., The complexity of theorem proving procedures, (Proc. 3rd ACM Conference on Theory of Computing (May 1970)), 151-158 · Zbl 0363.68125
[3] Karp, R. M., Reducibility among combinatorial problems, (TR3 (April 1972), Department of Computer Science, University of California at Berkeley) · Zbl 0366.68041
[4] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., (The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0326.68005
[5] Sethi, R., Complete register allocation problems, (5th Annual ACM Symp. on Theory of Computing (May 1973)) · Zbl 0308.68018
[6] Bruno, J.; Coffman, E. G.; Sethi, R., Scheduling independent tasks to reduce mean finishing time, CACM, 17, 382-387 (1974) · Zbl 0283.68039
[7] Garey, M. R.; Johnson, D. S., Complexity results for multiprocessor scheduling under resource constraints, (Proc. 8th Annual Princeton Conf. on Inf. Sci. and Systems (August 1974)) · Zbl 0365.90076
[8] Coffman, E. G.; Graham, R. L., Optimal scheduling for two-processor systems, Acta. Inf., 1, 200-213 (1972) · Zbl 0248.68023
[9] Fuji, M.; Kasami, T.; Ninomiya, N., Optimal sequence of two equivalent processors, SIAM J. Appl. Math., 17, 784-789 (1969) · Zbl 0205.48603
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.