{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T22:38:32Z","timestamp":1757543912970},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540167662"},{"type":"electronic","value":"9783540387466"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1986]]},"DOI":"10.1007\/3-540-16766-8_2","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T13:54:07Z","timestamp":1330178047000},"page":"12-25","source":"Crossref","is-referenced-by-count":5,"title":["Two processor scheduling is in NC"],"prefix":"10.1007","author":[{"given":"David","family":"Helmbold","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ernst","family":"Mayr","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"2_CR1","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1007\/BF00288685","volume":"1","author":"E.G. Coffman Jr.","year":"1972","unstructured":"Coffman, E.G., Jr., and R.L. Graham \u201cOptimal Scheduling for Two Processor Systems,\" Acta Informatica 1 (1972), pp. 200\u2013213.","journal-title":"Acta Informatica"},{"key":"2_CR2","unstructured":"Dolev, D., E. Upfal, and M. Warmuth, \u201cScheduling Trees in Parallel,\u201d In: Bertolazzi, P, Luccio, F. (eds.): VLSI: Algorithms and Architectures. Proceedings of the of the International Workshop on Parallel Computating and VLSI, Amalfi, Italy (May 1984): North-Holland 1985, p. 1\u201330."},{"key":"2_CR3","first-page":"784","volume":"17","author":"M. Fujii","year":"1969","unstructured":"Fujii, M., T. Kasami, and K. Ninamiya, \u201cOptimal Sequencing of Two Equivalent Processors,\" SIAM J. of Computing 17 (1969), pp. 784\u2013789.","journal-title":"SIAM J. of Computing"},{"issue":"3","key":"2_CR4","doi-asserted-by":"crossref","first-page":"766","DOI":"10.1145\/322326.322335","volume":"29","author":"H.N. Gabow","year":"1982","unstructured":"Gabow, H.N., \u201cAn Almost-linear Algorithm for Two-processor Scheduling,\u201d J.ACM 29,3 (1982), pp. 766\u2013780.","journal-title":"J.ACM"},{"key":"2_CR5","doi-asserted-by":"crossref","unstructured":"Gabow, H.N. and Tarjan, R.E., \u201cA Linear Time Algorithm for a Special Case of Disjoint Set Union\u201d, Proceedings of the 15th Ann. ACM Symposium on Theory of Computing (Boston, Mass., 1983), pp. 246\u2013251.","DOI":"10.1145\/800061.808753"},{"key":"2_CR6","unstructured":"Ghouil\u00e0-Houri, A., \u201cCharact\u00e9risation des graphes non orient\u00e9s dont on peut orienter les arr\u00eates de mani\u00e8re \u00e0 obtenir le graphe d'une relation d'ordre,\u201d C.R. Acad. Sci. Paris 254 (1962)."},{"key":"2_CR7","unstructured":"Helmbold, D. and E. Mayr, \u201cFast Scheduling Algorithms on Parallel Computers,\u201d STAN-CS-84-1025, Department of Computer Science, Stanford University (November 1984). To appear in Advances in Computing Research."},{"key":"2_CR8","unstructured":"Helmbold, D. and E. Mayr, \u201cTransitive Orientation and NC Algorithms,\u201d in preparation."},{"key":"2_CR9","doi-asserted-by":"crossref","first-page":"841","DOI":"10.1287\/opre.9.6.841","volume":"9","author":"H. T.C","year":"1961","unstructured":"Hu, T.C., \u201cParallel Sequencing and Assembly Line Problems,\u201d Operations Research 9 (1961), pp. 841\u2013848.","journal-title":"Operations Research"},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"Karp, R.M., E. Upfal, and A. Wigderson, \u201cConstructing a Perfect Matching is in Random NC,\u201d Proceedings of the 17th Ann. ACM Symposium on Theory of Computing (Providence, RI, 1985), pp. 22\u201332.","DOI":"10.1145\/22145.22148"},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"Karp, R.M., E. Upfal, and A. Wigderson, \u201cAre Search and Decision Problems Computationally Equivalent?,\u201d Proceedings of the 17th Ann. ACM Symposium on Theory of Computing (Providence, RI, 1985), pp. 464\u2013475.","DOI":"10.1145\/22145.22197"},{"key":"2_CR12","unstructured":"Kozen, D., U.V. Vazirani, and V.V. Vazirani, \u201cNC Algorithms for Comparability Graphs, Interval Graphs, and Testing for Unique Perfect Matching,\u201d to appear."},{"key":"2_CR13","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1137\/0208031","volume":"8","author":"C.H. Papadimitriou","year":"1979","unstructured":"Papadimitriou, C.H. and Yannakakis, M., \u201cScheduling Interval-Ordered Tasks,\u201d SIAM J. Computing 8,3 (1979).","journal-title":"SIAM J. Computing"},{"issue":"1","key":"2_CR14","doi-asserted-by":"crossref","first-page":"160","DOI":"10.4153\/CJM-1971-016-5","volume":"23","author":"A. Pnueli","year":"1971","unstructured":"Pnueli, A., A. Lempel, and S. Even, \u201cTransitive Orientation of Graphs and Identification of Permutation Graphs,\u201d Can. J. Math. 23,1 (1971), pp. 160\u2013175.","journal-title":"Can. J. Math."},{"key":"2_CR15","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1016\/S0022-0000(75)80008-0","volume":"10","author":"J.D. Ullman","year":"1975","unstructured":"Ullman, J.D., \u201cNP-complete Scheduling Problems,\" J. Comput. System Sci. 10 (1975), pp. 384\u2013393.","journal-title":"J. Comput. System Sci."},{"key":"2_CR16","doi-asserted-by":"crossref","unstructured":"Vazirani, U.V. and V.V. Vazirani, \u201cThe Two-Processor Scheduling Problem is in RNC,\u201d Proceedings of the 17th Ann. ACM Symposium on Theory of Computing (Providence, RI, 1985), pp. 11\u201321.","DOI":"10.1145\/22145.22147"}],"container-title":["Lecture Notes in Computer Science","VLSI Algorithms and Architectures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-16766-8_2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:11:08Z","timestamp":1605625868000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-16766-8_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540167662","9783540387466"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-16766-8_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1986]]}}}