{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:12:55Z","timestamp":1725455575106},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540637578"},{"type":"electronic","value":"9783540696438"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/bfb0024508","type":"book-chapter","created":{"date-parts":[[2005,11,19]],"date-time":"2005-11-19T07:30:56Z","timestamp":1132385456000},"page":"333-341","source":"Crossref","is-referenced-by-count":1,"title":["A measure of parallelization for the lexicographically first maximal subgraph problems"],"prefix":"10.1007","author":[{"given":"Ryuhei","family":"Uehara","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,17]]},"reference":[{"key":"27_CR1","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N. Alon","year":"1986","unstructured":"N. Alon, L. Babai, and A. Itai. A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem. Journal of Algorithms, 7:567\u2013583, 1986.","journal-title":"Journal of Algorithms"},{"key":"27_CR2","unstructured":"Z.-Z. Chen. Personal communication. 1997."},{"key":"27_CR3","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"S.A. Cook","year":"1985","unstructured":"S.A. Cook. A Taxonomy of Problems with Fast Parallel Algorithms. Information and Control, 64:2\u201322, 1985.","journal-title":"Information and Control"},{"key":"27_CR4","doi-asserted-by":"crossref","unstructured":"K. Diks, O. Garrido, and A. Lingas. Parallel algorithms for finding maximal k-dependent sets and maximal f-matchings. In ISA '91 Algorithms, pages 385\u2013395. Lecture Notes in Computer Science Vol. 557, Springer-Verlag, 1991.","DOI":"10.1007\/3-540-54945-5_82"},{"key":"27_CR5","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/0020-0190(88)90164-0","volume":"28","author":"H. Gazit","year":"1988","unstructured":"H. Gazit and L. Miller. An Improved Parallel Algorithm That Computes the BFS Numbering of a Directed Graph. Information Processing Letters, 28:61\u201365, 1988.","journal-title":"Information Processing Letters"},{"issue":"2","key":"27_CR6","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1137\/0218029","volume":"18","author":"M. Goldberg","year":"1989","unstructured":"M. Goldberg and T. Spencer. A New Parallel Algorithm for the Maximal Independent Set Problem. SIAM Journal on Computing, 18(2):419\u2013427, 1989.","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"27_CR7","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1137\/0402028","volume":"2","author":"M. Goldberg","year":"1989","unstructured":"M. Goldberg and T. Spencer. Constructing a Maximal Independent Set in Parallel. SIAM J. Disc. Math., 2(3):322\u2013328, 1989.","journal-title":"SIAM J. Disc. Math."},{"key":"27_CR8","doi-asserted-by":"crossref","unstructured":"R. Greenlaw, H.J. Hoover, and W.L. Ruzzo. Limits to Parallel Computation. Oxford University Press, 1995.","DOI":"10.1093\/oso\/9780195085914.001.0001"},{"key":"27_CR9","unstructured":"F. Harary. Graph Theory. Addison-Wesley, 1972."},{"key":"27_CR10","doi-asserted-by":"crossref","first-page":"526","DOI":"10.1016\/S0196-6774(96)90033-5","volume":"20","author":"K. Iwama","year":"1996","unstructured":"K. Iwama and C. Iwamoto. \u03b1-Connectivity: A Gradually Nonparallel Graph Problem. Journal of Algorithms, 20:526\u2013544, 1996.","journal-title":"Journal of Algorithms"},{"key":"27_CR11","doi-asserted-by":"crossref","unstructured":"R.M. Karp and V. Ramachandran. Parallel Algorithms for Shared-Memory Machines. In J. van Leeuwen, editor, The Handbook of Theoretical Computer Science, vol. I: Algorithms and Complexity, pages 870\u2013941. MIT Press, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"issue":"4","key":"27_CR12","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1145\/4221.4226","volume":"32","author":"R.M. Karp","year":"1985","unstructured":"R.M. Karp and A. Wigderson. A Fast Parallel Algorithm for the Maximal Independent Set Problem. Journal of American Computing Machinery, 32(4):762\u2013773, 1985.","journal-title":"Journal of American Computing Machinery"},{"key":"27_CR13","doi-asserted-by":"crossref","unstructured":"D.C. Kozen. The Design and Analysis of Algorithms. Springer-Verlag, 1992.","DOI":"10.1007\/978-1-4612-4400-4"},{"issue":"4","key":"27_CR14","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M. Luby","year":"1986","unstructured":"M. Luby. A Simple Parallel Algorithm for the Maximal Independent Set Problem. SIAM Journal on Computing, 15(4):1036\u20131053, 1986.","journal-title":"SIAM Journal on Computing"},{"key":"27_CR15","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/BF02088292","volume":"22","author":"S. Miyano","year":"1989","unstructured":"S. Miyano. The Lexicographically First Maximal Subgraph Problems: PCompleteness and NC Algorithms. Mathematical Systems Theory, 22:47\u201373, 1989.","journal-title":"Mathematical Systems Theory"},{"key":"27_CR16","unstructured":"C.H. Papadimitriou. Computational Complexity. Addison-Wesley Publishing Company, 1994."},{"key":"27_CR17","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1006\/jagm.1993.1008","volume":"14","author":"D. Pearson","year":"1993","unstructured":"D. Pearson and V.V. Vazirani. Efficient Sequential and Parallel Algorithms for Maximal Bipartite Sets. Journal of Algorithms, 14:171\u2013179, 1993.","journal-title":"Journal of Algorithms"},{"key":"27_CR18","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0304-3975(94)00221-4","volume":"148","author":"T. Shoudai","year":"1995","unstructured":"T. Shoudai and S. Miyano. Using Maximal Independent Sets to Solve Problems in Parallel. Theoretical Computer Science, 148:57\u201365, 1995.","journal-title":"Theoretical Computer Science"},{"key":"27_CR19","unstructured":"S. Toda. Personal communication. 1997."}],"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\/BFb0024508","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,20]],"date-time":"2021-07-20T01:58:57Z","timestamp":1626746337000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0024508"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540637578","9783540696438"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/bfb0024508","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}