{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:55:57Z","timestamp":1725663357734},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540172185"},{"type":"electronic","value":"9783540474159"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1987]]},"DOI":"10.1007\/3-540-17218-1_59","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T19:13:22Z","timestamp":1330197202000},"page":"188-203","source":"Crossref","is-referenced-by-count":4,"title":["Applications of parallel scheduling to perfect graphs"],"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,4]]},"reference":[{"key":"15_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. Aho","year":"1974","unstructured":"A. Aho, J. Hopcroft, and J. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, New York, 1974."},{"key":"15_CR2","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1007\/BF00288685","volume":"1","author":"E.G. Coffman Jr.","year":"1972","unstructured":"E.G. Coffman, Jr., and R. Graham. Optimal scheduling for two processor systems. Acta Informatica, 1:200\u2013213, 1972.","journal-title":"Acta Informatica"},{"key":"15_CR3","unstructured":"D. Dolev, E. Upfal, and M. Warmuth. Scheduling trees in parallel. In Bertolazzi, P, Luccio, F. (eds.): VLSI: Algorithms and Architectures. Proceedings of the International Workshop on Parallel Computating and VLSI, pages 1\u201330, North-Holland, 1985."},{"key":"15_CR4","doi-asserted-by":"crossref","unstructured":"S. Fortune and J. Wyllie. Parallelism in random access machines. In Proceedings of the 10th Ann. ACM Symp. on Theory of Computing (San Diego, CA), pages 114\u2013118, 1978.","DOI":"10.1145\/800133.804339"},{"issue":"4","key":"15_CR5","doi-asserted-by":"crossref","first-page":"784","DOI":"10.1137\/0117070","volume":"17","author":"M. Fujii","year":"1969","unstructured":"M. Fujii, T. Kasami, and K. Ninamiya. Optimal sequencing of two equivalent processors. SIAM J. Appl. Math., 17(4):784\u2013789, 1969.","journal-title":"SIAM J. Appl. Math."},{"issue":"3","key":"15_CR6","doi-asserted-by":"crossref","first-page":"766","DOI":"10.1145\/322326.322335","volume":"29","author":"H. Gabow","year":"1982","unstructured":"H. Gabow. An almost-linear algorithm for two-processor scheduling. JACM, 29(3):766\u2013780, 1982.","journal-title":"JACM"},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"H. Gabow and R. Tarjan. A linear time algorithm for special case of disjoint set union. In Proceedings of the 15th Ann. ACM Symp. on Theory of Computing (Boston, Mass.), pages 246\u2013251, 1983.","DOI":"10.1145\/800061.808753"},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"P. Gilmore and A. Hoffman. A characterization of comparability graphs and of interval graphs. Canad. J. Math, 16, 1964.","DOI":"10.4153\/CJM-1964-055-5"},{"key":"15_CR9","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M. Golumbic","year":"1980","unstructured":"M. Golumbic. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, 1980."},{"issue":"1","key":"15_CR10","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/0095-8956(77)90049-1","volume":"22","author":"M. Golumbic","year":"1977","unstructured":"M. Golumbic. Comparability graphs and a new matroid. J. Combinatorial Theory (B), 22(1):68\u201390, 1977.","journal-title":"J. Combinatorial Theory (B)"},{"key":"15_CR11","unstructured":"D. Helmbold and E. Mayr. Fast scheduling algorithms on parallel computers. Advances in Computing Research, 1986. to appear."},{"key":"15_CR12","doi-asserted-by":"crossref","unstructured":"D. Helmbold and E. Mayr. Two processor scheduling is in NC. In Proc. 1986 Aegean Workshop on Computing: VLSI Algorithms and Architectures, July 1986.","DOI":"10.1007\/3-540-16766-8_2"},{"key":"15_CR13","doi-asserted-by":"crossref","unstructured":"R. Karp, E. Upfal, and A. Wigderson. Are search and decision problems computationally equivalent? In Proceedings of the 17th Ann. ACM Symp. on Theory of Computing (Providence, RI), pages 465\u2013475, 1985.","DOI":"10.1145\/22145.22197"},{"key":"15_CR14","doi-asserted-by":"crossref","unstructured":"R. Karp, E. Upfal, and A. Wigderson. Constructing a perfect matching is in random NC. In Proceedings of the 17th Ann. ACM Symp. on Theory of Computing (Providence, RI), pages 22\u201332, 1985.","DOI":"10.1145\/22145.22148"},{"issue":"4","key":"15_CR15","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1145\/4221.4226","volume":"32","author":"R. Karp","year":"1985","unstructured":"R. Karp and A. Wigderson. A fast parallel algorithm for the maximal independent set problem. J.ACM, 32(4):762\u2013773, 1985.","journal-title":"J.ACM"},{"key":"15_CR16","doi-asserted-by":"crossref","unstructured":"D. Kozen, U. Vazirani, and V. Vazirani. NC algorithms for comparability graphs, interval graphs, and testing for unique perfect matching. In 5th Conf. Found. of Software Tech. and Theor. Comp. Sci. (New Dehli), 1985.","DOI":"10.1007\/3-540-16042-6_28"},{"key":"15_CR17","doi-asserted-by":"crossref","unstructured":"M. Luby. A simple parallel algorithm for the maximal independent set problem. In Proceedings of the 17th Ann. ACM Symp. on Theory of Computing (Providence, RI), pages 1\u201310, 1985.","DOI":"10.1145\/22145.22146"},{"key":"15_CR18","unstructured":"K. Mulmuley, U. Vazirani, and V. Vazirani. Parallel algorithms for rank and matching. private communication."},{"key":"15_CR19","doi-asserted-by":"crossref","unstructured":"C. Papadimitriou and M. Yannakakis. Scheduling interval-ordered tasks. SIAM J. Computing, 8(3), 1979.","DOI":"10.1137\/0208031"},{"key":"15_CR20","doi-asserted-by":"crossref","unstructured":"N. Pippenger. On simultaneous resource bounds. In Proceedings of the 20th IEEE Symp. on Foundations of Computer Science, pages 307\u2013311, 1979.","DOI":"10.1109\/SFCS.1979.29"},{"issue":"1","key":"15_CR21","doi-asserted-by":"crossref","first-page":"160","DOI":"10.4153\/CJM-1971-016-5","volume":"23","author":"A. Pnueli","year":"1971","unstructured":"A. Pnueli, A. Lempel, and S. Even. Transitive orientation of graphs and identification of permutation graphs. Can. J. Math., 23(1):160\u2013175, 1971.","journal-title":"Can. J. Math."},{"issue":"1","key":"15_CR22","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0196-6774(82)90008-6","volume":"3","author":"Y. Shiloach","year":"1982","unstructured":"Y. Shiloach and U. Vishkin. An O(log n) parallel connectivity algorithm. J. Algorithms, 3(1):57\u201363, 1982.","journal-title":"J. Algorithms"},{"issue":"3","key":"15_CR23","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1016\/S0022-0000(75)80008-0","volume":"10","author":"J. Ullman","year":"1975","unstructured":"J. Ullman. NP-complete scheduling problems. J. Comput. System Sci., 10(3):384\u2013393, 1975.","journal-title":"J. Comput. System Sci."},{"key":"15_CR24","doi-asserted-by":"crossref","unstructured":"U. Vazirani and V. Vazirani. The two-processor scheduling problem is in RNC. In Proceedings of the 17th Ann. ACM Symp. on Theory of Computing (Providence, RI), pages 11\u201321, 1985.","DOI":"10.1145\/22145.22147"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-17218-1_59.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:12:52Z","timestamp":1605643972000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-17218-1_59"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987]]},"ISBN":["9783540172185","9783540474159"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-17218-1_59","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1987]]}}}