{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:56:34Z","timestamp":1725663394435},"publisher-location":"Berlin, Heidelberg","reference-count":9,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540542339"},{"type":"electronic","value":"9783540475163"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-54233-7_152","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T17:38:31Z","timestamp":1330191511000},"page":"417-428","source":"Crossref","is-referenced-by-count":8,"title":["A parallel algorithm for two processors precedence constraint scheduling"],"prefix":"10.1007","author":[{"given":"Hermann","family":"Jung","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maria","family":"Serna","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul","family":"Spirakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"32_CR1","unstructured":"M. J. Atallah, P. Callaham, and M. T. Goodrich. P-complete geometric problems. SPAA 90"},{"key":"32_CR2","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1007\/BF00288685","volume":"1","author":"E. G. Coffman","year":"1972","unstructured":"E. G. Coffman, and R. L. Graham. Optimal scheduling for two processors systems. Acta Informatica, 1:200\u2013213, 1972.","journal-title":"Acta Informatica"},{"key":"32_CR3","doi-asserted-by":"crossref","first-page":"657","DOI":"10.1137\/0210049","volume":"10","author":"E. Dekel","year":"1981","unstructured":"E. Dekel, D. Nassimi, and S. Sahni. Parallel matrix and graph algorithms. SIAM Journal of computing, 10:657\u2013675, 1981.","journal-title":"SIAM Journal of computing"},{"key":"32_CR4","first-page":"784","volume":"17","author":"M. Fujii","year":"1969","unstructured":"M. Fujii, T. Kasami, and K. Ninomiya. Optimal sequencing of two equivalent processors. SIAM Journal of computing, 17:784\u2013789, 1969.","journal-title":"SIAM Journal of computing"},{"issue":"3","key":"32_CR5","doi-asserted-by":"crossref","first-page":"766","DOI":"10.1145\/322326.322335","volume":"29","author":"H. N. Gabow","year":"1982","unstructured":"H. N. Gabow. An almost linear time algorithm for two processors scheduling. Journal of the ACM, 29(3):766\u2013780, 1982.","journal-title":"Journal of the ACM"},{"key":"32_CR6","volume-title":"Computers and Intractability: A Guide to the theory of NP completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey, and D. S. Johnson. Computers and Intractability: A Guide to the theory of NP completeness. Freeman, San Francisco, 1979."},{"key":"32_CR7","first-page":"12","volume":"86","author":"D. Hembold","year":"1986","unstructured":"D. Hembold, and E. Mayr. Two processor scheduling is in NC. AWOC 86, pp. 12\u201325, 1986.","journal-title":"AWOC"},{"key":"32_CR8","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1016\/S0022-0000(75)80008-0","volume":"10","author":"J. D. Ullman","year":"1975","unstructured":"J. D. Ullman. NP-complete scheduling problems. Journal of Computer and System Sciences, 10:384\u2013393, 1975.","journal-title":"Journal of Computer and System Sciences"},{"key":"32_CR9","first-page":"11","volume":"85","author":"U. V. Vazirani","year":"1985","unstructured":"U. V. Vazirani, and V. V. Vazirani. The two processor scheduling is in RNC. STOC 85, pp. 11\u201321, 1985.","journal-title":"STOC"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-54233-7_152.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T21:20:20Z","timestamp":1619558420000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-54233-7_152"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540542339","9783540475163"],"references-count":9,"URL":"https:\/\/doi.org\/10.1007\/3-540-54233-7_152","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1991]]}}}