{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:11:02Z","timestamp":1725664262666},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540590712"},{"type":"electronic","value":"9783540491835"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-59071-4_51","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T12:02:43Z","timestamp":1330257763000},"page":"232-241","source":"Crossref","is-referenced-by-count":1,"title":["The maximal f-dependent set problem for planar graphs is in NC"],"prefix":"10.1007","author":[{"given":"Zhi -Zhong","family":"Chen","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"19_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, J. Algorithms\n7 (1986) 567\u2013583.","journal-title":"J. Algorithms"},{"key":"19_CR2","volume-title":"Graph Theory with Applications","author":"J. A. Bondy","year":"1980","unstructured":"J. A. Bondy and U. S. R. Murty, Graph Theory with Applications (North-Holland, New York, 1980)."},{"key":"19_CR3","unstructured":"Z.-Z. Chen and X. He, Parallel Algorithms for Maximal Cycle-Free Sets, Submitted for publication."},{"key":"19_CR4","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0196-6774(89)90022-9","volume":"10","author":"M. Chrobak","year":"1986","unstructured":"M. Chrobak and M. Yung, Fast Algorithms for Edge-Coloring Planar Graphs, J. Algorithms\n10 (1986) 35\u201351.","journal-title":"J. Algorithms"},{"key":"19_CR5","first-page":"385","volume-title":"Lecture Notes in Computer Science, Vol. 557","author":"K. Diks","year":"1991","unstructured":"K. Diks, O. Garrido and A. Lingas, Parallel Algorithm for Finding maximal k-Dependent Sets and Maximal f-Matchings, in: Proc. 2nd International Symp. on Algorithms, Lecture Notes in Computer Science, Vol. 557 (Springer, Berlin, 1991) 385\u2013395."},{"key":"19_CR6","volume-title":"Efficient Parallel Algorithms","author":"A. Gibbons","year":"1988","unstructured":"A. Gibbons and W. Rytter, Efficient Parallel Algorithms (Cambridge University Press, Cambridge, 1988)."},{"key":"19_CR7","doi-asserted-by":"crossref","unstructured":"A.V. Goldberg, S.A. Plotkin and G.E. Shannon, Parallel Symmetry-Breaking in Sparse Graphs, in: Proc. 19th ACM Symp. on Theory of Computing (ACM, 1987) 315\u2013324.","DOI":"10.1145\/28395.28429"},{"key":"19_CR8","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":"19_CR9","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.\n2 (1989) 322\u2013328.","journal-title":"SIAM J. Disc. Math."},{"key":"19_CR10","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0020-0190(86)90144-4","volume":"22","author":"A. Israeli","year":"1986","unstructured":"A. Israeli and A. Itai, A Fast and Simple Randomized Parallel Algorithm for Maximal Matching, Inform. Process. Lett.\n22 (1986) 77\u201380.","journal-title":"Inform. Process. Lett."},{"key":"19_CR11","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0020-0190(86)90141-9","volume":"22","author":"A. Israeli","year":"1986","unstructured":"A. Israeli and Y. Shiloach, An Improved Maximal Matching Parallel Algorithm, Inform. Process. Lett.\n22 (1986) 57\u201360.","journal-title":"Inform. Process. Lett."},{"key":"19_CR12","first-page":"868","volume-title":"Handbook of Theoretical Computer Science Vol. A","author":"R.M. Karp","year":"1990","unstructured":"R.M. Karp and V. Ramachandran, Parallel Algorithms for Shared Memory Machines, in: J. van Leeuwen ed., Handbook of Theoretical Computer Science Vol. A (Elsevier, Amsterdam, 1990) 868\u2013941."},{"key":"19_CR13","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. ACM\n32 (1985) 762\u2013773.","journal-title":"J. ACM"},{"key":"19_CR14","unstructured":"L. Lov\u00e1sz and M.D. Plummer, Matching Theory, Annals of Discrete Mathematics (29), North-Holland Mathematics Studies 121 (Elsevier Science Publisher B.V., 1986)."},{"key":"19_CR15","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 J. Comput.\n15 (1986) 1036\u20131053.","journal-title":"SIAM J. Comput."},{"key":"19_CR16","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, J. Algorithms\n14 (1993), 171\u2013179.","journal-title":"J. Algorithms"},{"key":"19_CR17","first-page":"126","volume-title":"Lecture Notes in Computer Science, Vol. 570","author":"T. Shoudai","year":"1991","unstructured":"T. Shoudai and S. Miyano, Using Maximal Independent Sets to Solve Problems in Parallel, in: Proc. 17th International Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, Vol. 570 (Springer, Berlin, 1991) 126\u2013134."},{"key":"19_CR18","unstructured":"L.G. Valiant, Parallel Computation, in: Proc. 7th IBM Symposium on Mathematical Foundations of Computer Science (1982) 173\u2013189."}],"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-59071-4_51.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T21:22:27Z","timestamp":1619558547000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-59071-4_51"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540590712","9783540491835"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-59071-4_51","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}