{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:01:58Z","timestamp":1725483718480},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540678236"},{"type":"electronic","value":"9783540449294"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44929-9_9","type":"book-chapter","created":{"date-parts":[[2007,5,5]],"date-time":"2007-05-05T09:20:53Z","timestamp":1178356853000},"page":"100-111","source":"Crossref","is-referenced-by-count":0,"title":["An Efficient Parallel Algorithm for Scheduling Interval Ordered Tasks"],"prefix":"10.1007","author":[{"given":"Yoojin","family":"Chung","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kunsoo","family":"Park","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hyuk-Chul","family":"Kwon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,8,24]]},"reference":[{"key":"9_CR1","doi-asserted-by":"crossref","unstructured":"M. Bartusch, R. H. Mohring, and F. J. Radermacher, \u201cM-machine unit time scheduling: A report of ongoing research,\u201dLecture Notes in Economics and Mathematical Systems 304, Springer-Verlag (1988) 165\u2013212.","DOI":"10.1007\/978-3-642-46631-1_14"},{"issue":"1","key":"9_CR2","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1142\/S0129054199000058","volume":"10","author":"Y. Chung","year":"1999","unstructured":"Y. Chung, K. Park, and Y. Cho, \u201cParallel maximum matching algorithms in interval graphs,\u201d Int\u2019l. J. Foundations of Comput. Science 10, 1 (1999) 47\u201360.","journal-title":"Int\u2019l. J. Foundations of Comput. Science"},{"key":"9_CR3","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1007\/BF00288685","volume":"1","author":"E. Coffman","year":"1972","unstructured":"E. Coffman and R. Graham, \u201cOptimal scheduling for two processor systems,\u201d Acta Informatica 1 (1972) 200\u2013213.","journal-title":"Acta Informatica"},{"issue":"4","key":"9_CR4","doi-asserted-by":"publisher","first-page":"770","DOI":"10.1137\/0217049","volume":"17","author":"R. Cole","year":"1988","unstructured":"R. Cole, \u201cParallel merge sort,\u201d SIAM J. Comput. 17, 4 (1988) 770\u2013785.","journal-title":"SIAM J. Comput."},{"key":"9_CR5","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0743-7315(84)90004-2","volume":"1","author":"E. Dekel","year":"1984","unstructured":"E. Dekel and S. Sahni, \u201cA parallel matching algorithm for convex bipartite graphs and applications to scheduling,\u201d J. Parallel Distrib. Comput. 1 (1984) 185\u2013205.","journal-title":"J. Parallel Distrib. Comput."},{"key":"9_CR6","doi-asserted-by":"publisher","first-page":"784","DOI":"10.1137\/0117070","volume":"17","author":"M. Fujii","year":"1969","unstructured":"M. Fujii, T. Kasami, and K. Ninomiya, \u201cOptimal sequencing of two equivalent processors,\u201d SIAM J. Appl. Math. 17(1969) 784\u2013789.","journal-title":"SIAM J. Appl. Math."},{"issue":"3","key":"9_CR7","doi-asserted-by":"publisher","first-page":"766","DOI":"10.1145\/322326.322335","volume":"29","author":"H.N. Gabow","year":"1982","unstructured":"H.N. Gabow, \u201cAn almost-linear algorithm for two-processor scheduling,\u201d J. ACM 29, 3 (1982) 766\u2013780.","journal-title":"J. ACM"},{"key":"9_CR8","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1006\/jpdc.1994.1053","volume":"21","author":"Z. Galil","year":"1994","unstructured":"Z. Galil and K. Park, \u201cParallel algorithms for dynamic programming recurrences with more than O(1) dependency,\u201dJ. Parallel Distrib. Comput. 21, (1994) 213\u2013222.","journal-title":"J. Parallel Distrib. Comput."},{"key":"9_CR9","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1145\/321958.321967","volume":"23","author":"M. R. Garey","year":"1976","unstructured":"M. R. Garey and D. S. Johnson, \u201cScheduling tasks with nonuniform deadlines on two processors,\u201dJ. ACM 23 (1976) 461\u2013467.","journal-title":"J. ACM"},{"key":"9_CR10","volume-title":"Graph theory and perfect graphs","author":"M.C. Golumbic","year":"1980","unstructured":"M.C. Golumbic, Graph theory and perfect graphs, Academic Press, New York, 1980."},{"issue":"4","key":"9_CR11","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1137\/0216050","volume":"16","author":"D. Helmbold","year":"1987","unstructured":"D. Helmbold and E. Mayr, \u201cTwo processor scheduling is in NC,\u201d SIAM J. Comput. 16, 4(1987) 747\u2013759.","journal-title":"SIAM J. Comput."},{"key":"9_CR12","doi-asserted-by":"publisher","first-page":"841","DOI":"10.1287\/opre.9.6.841","volume":"9","author":"T. C. Hu","year":"1961","unstructured":"T. C. Hu, \u201cParallel sequencing and assembly line problems,\u201dOper. Res. 9 (1961) 841\u2013848.","journal-title":"Oper. Res."},{"key":"9_CR13","unstructured":"E. L. Lawler, J. K. Lenstra, A. H. G. R. Kan, and D. B. Shmoys, \u201cSequencing and scheduling: Algorithms and complexity,\u201dTechnical report, Centrum voor Wiskunde en Informatica, 1989."},{"key":"9_CR14","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1080\/10637199608915542","volume":"8","author":"E. Mayr","year":"1996","unstructured":"E. Mayr, \u201cScheduling interval orders in parallel,\u201d Parallel Algorithms and Applications 8 (1996) 21\u201334.","journal-title":"Parallel Algorithms and Applications"},{"key":"9_CR15","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1137\/0208031","volume":"8","author":"C. H. Papadimitriou","year":"1979","unstructured":"C. H. Papadimitriou and M Yannakakis, \u201cScheduling interval-ordered tasks,\u201d SIAM J. Comput. 8 (1979), pp. 405\u2013409.","journal-title":"SIAM J. Comput."},{"key":"9_CR16","doi-asserted-by":"crossref","unstructured":"H. Jung, M. Serna and P. Spirakis, \u201cA parallel algorithm for two processors precedence constraint scheduling,\u201dProc. Int\u2019l Colloquium on Automata, Languages and Programming (1991) pp. 417\u2013428.","DOI":"10.1007\/3-540-54233-7_152"},{"key":"9_CR17","unstructured":"D. Kozen, U.V. Vazirani and V.V. Vazirani, \u201cNC algorithms for cocomparability graphs, interval graphs, and unique perfect matchings,\u201d Proc. Foundations of Software Technology and Theoretical Computer Science (1985) pp. 496\u2013503."},{"key":"9_CR18","first-page":"114","volume":"3","author":"A. Moitra","year":"1989","unstructured":"A. Moitra and R. Johnson, \u201cA parallel algorithm for maximum matching on interval graphs,\u201dProc. Int\u2019l Conference on Parallel Processing 3 (1989) pp. 114\u2013120.","journal-title":"Proc. Int\u2019l Conference on Parallel Processing"},{"key":"9_CR19","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1006\/jagm.1997.0895","volume":"26","author":"S. Sunder","year":"1998","unstructured":"S. Sunder and X. He, \u201cScheduling interval ordered tasks in parallel,\u201d J. Algorithm 26 (1998), pp. 34\u201347.","journal-title":"J. Algorithm"},{"key":"9_CR20","unstructured":"J. D. Ulman, Complexity of sequencing problems, in \u201cComputer and job scheduling theory\u201d (E. G. Coffman, Ed.), Wiley, 1976."},{"key":"9_CR21","unstructured":"U.V. Vazirani and V.V. Vazirani, \u201cThe two processor scheduling is in random NC,\u201dSIAM J. Comput. (1989) pp. 1140\u20131148."}],"container-title":["Lecture Notes in Computer Science","Theoretical Computer Science: Exploring New Frontiers of Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44929-9_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T14:41:00Z","timestamp":1556376060000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44929-9_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540678236","9783540449294"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-44929-9_9","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}