{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:00:14Z","timestamp":1725663614454},"publisher-location":"Berlin, Heidelberg","reference-count":8,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540551218"},{"type":"electronic","value":"9783540467359"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-55121-2_12","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T09:47:34Z","timestamp":1330249654000},"page":"126-134","source":"Crossref","is-referenced-by-count":0,"title":["Using maximal independent sets to solve problems in parallel"],"prefix":"10.1007","author":[{"given":"Takayoshi","family":"Shoudai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Satoru","family":"Miyano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,5]]},"reference":[{"key":"12_CR1","doi-asserted-by":"crossref","unstructured":"B. Berger, J. Rompel and P.W. Shor, Efficient NC algorithm for set cover with application to learning and geometry, Proc. 30th IEEE FOCS (1989) 54\u201359.","DOI":"10.1109\/SFCS.1989.63455"},{"key":"12_CR2","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, Taxonomy of problems with fast parallel algorithms, Inform. Contr.\n64 (1985) 2\u201322.","journal-title":"Inform. Contr."},{"key":"12_CR3","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 J. comput.\n18 (1989) 419\u2013427.","journal-title":"SIAM J. comput."},{"key":"12_CR4","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, J. Assoc. Comput. Mach.\n32 (1985) 762\u2013773.","journal-title":"J. Assoc. Comput. Mach."},{"key":"12_CR5","doi-asserted-by":"crossref","unstructured":"M. Luby, A simple parallel algorithm for the maximal independent set problem, Proc. 17th ACM STOC (1985) 1\u201310.","DOI":"10.1145\/22145.22146"},{"key":"12_CR6","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: P-completeness and NC algorithms, Math. Systems Theory\n22 (1989) 47\u201373.","journal-title":"Math. Systems Theory"},{"key":"12_CR7","unstructured":"S. Miyano, S. Shiraishi and T. Shoudai, A list of P-complete problems, RIFIS-TR-CS-17, Research Institute of Fundamental Information Science, Kyushu University, 1989 (revised in December, 1990)."},{"key":"12_CR8","unstructured":"T. Shoudai and S. Miyano, Bounded degree maximal subgraph problems are in NC, Proc. Toyohashi Symposium on Theoretical Computer Science (1990) 97\u2013101."}],"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-55121-2_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:28:01Z","timestamp":1619573281000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-55121-2_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540551218","9783540467359"],"references-count":8,"URL":"https:\/\/doi.org\/10.1007\/3-540-55121-2_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1992]]}}}