{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:22:53Z","timestamp":1725664973317},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540606185"},{"type":"electronic","value":"9783540484875"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60618-1_82","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T20:48:47Z","timestamp":1330289327000},"page":"275-289","source":"Crossref","is-referenced-by-count":0,"title":["NC algorithms for partitioning planar graphs into induced forests and approximating NP-hard problems"],"prefix":"10.1007","author":[{"given":"Zhi-Zhong","family":"Chen","sequence":"first","affiliation":[]},{"given":"Xin","family":"He","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"22_CR1","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0304-3975(85)90222-1","volume":"38","author":"T. Asano","year":"1985","unstructured":"T. Asano, An approach to the subgraph homeomorphism problem, Theoret. Comput. Sci. 38, 249\u2013267 (1985).","journal-title":"Theoret. Comput. Sci."},{"key":"22_CR2","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B. S. Baker","year":"1994","unstructured":"B.S. Baker, Approximation algorithms for NP-complete problems on planar graphs, J. ACM 41, 153\u2013180 (1994).","journal-title":"J. ACM"},{"key":"22_CR3","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02760181","volume":"6","author":"G. Chartrand","year":"1968","unstructured":"G. Chartrand, H.V. Kronk, and C.E. Wall, The point-arboricity of a graph, Israel J. Math. 6, 169\u2013175 (1968).","journal-title":"Israel J. Math."},{"key":"22_CR4","doi-asserted-by":"crossref","first-page":"612","DOI":"10.1112\/jlms\/s1-44.1.612","volume":"44","author":"G. Chartrand","year":"1969","unstructured":"G. Chartrand and H.V. Kronk, The point-arboricity of planar graphs, J. London Math. Soc. 44, 612\u2013616 (1969).","journal-title":"J. London Math. Soc."},{"key":"22_CR5","volume-title":"Graphs and Digraphs","author":"G. Chartrand","year":"1986","unstructured":"G. Chartrand and L. Lesniak, Graphs and Digraphs (2nd ed.), (Wadsworth, Belmont, 1986).","edition":"2nd ed."},{"key":"22_CR6","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/S0019-9958(86)80023-7","volume":"70","author":"R. Cole","year":"1986","unstructured":"R. Cole and U. Vishikin, Deterministic coin tossing with applications to optimal parallel list ranking, Inform. and Control 70, 32\u201353 (1986).","journal-title":"Inform. and Control"},{"key":"22_CR7","doi-asserted-by":"crossref","unstructured":"H. Gazit, Optimal EREW parallel algorithms for connectivity, ear Decomposition and st-Numbering of planar graphs, in \u201cProceedings, 5th IEEE International Parallel Processing Symposium 1991,\u201d; pp. 84\u201391.","DOI":"10.1109\/IPPS.1991.153761"},{"key":"22_CR8","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/0012-365X(91)90166-Y","volume":"91","author":"W. Goddard","year":"1991","unstructured":"W. Goddard, Acyclic colorings of graphs, Discrete Math. 91, 91\u201393 (1991).","journal-title":"Discrete Math."},{"key":"22_CR9","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1137\/0218020","volume":"18","author":"T. Hagerup","year":"1989","unstructured":"T. Hagerup, M. Chrobak, and K. Diks, Optimal parallel 5-colouring of planar graphs, SIAM J. Comput. 18, 288\u2013300 (1989).","journal-title":"SIAM J. Comput."},{"key":"22_CR10","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0196-6774(88)90007-7","volume":"9","author":"X. He","year":"1988","unstructured":"X. He, Binary tree algebraic computation and parallel algorithms for simple graphs, J. Algorithms 9, 92\u2013113 (1988).","journal-title":"J. Algorithms"},{"key":"22_CR11","doi-asserted-by":"crossref","unstructured":"R. M. Karp and V. Ramachandran, \u201cA survey of parallel algorithms for shared-memory machines,\u201d; in \u201cHandbook of Theoretical Computer Science, Volume A: Algorithms and Complexity,\u201d; The MIT Press\/Elsevier, 1990, 869\u2013941.","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"key":"22_CR12","doi-asserted-by":"crossref","unstructured":"P.N. Klein and S. Subramaniam, A linear-processor polylog-time algorithm for shortest paths in planar graphs, in: Proceedings of 31st IEEE Symposium on Foundations of Computer Science (IEEE, 1993) 173\u2013182.","DOI":"10.1109\/SFCS.1993.366861"},{"key":"22_CR13","doi-asserted-by":"crossref","unstructured":"G.L. Miller and J.H. Reif, Parallel tree contraction and its applications, in: Proceedings of 26th IEEE Symposium on Foundations of Computer Science (IEEE, 1985) 478\u2013489.","DOI":"10.1109\/SFCS.1985.43"},{"key":"22_CR14","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1002\/jgt.3190140108","volume":"14","author":"K. S. Poh","year":"1990","unstructured":"K.S. Poh, On the linear vertex-arboricity of a planar graph, J. Graph Theory 14, 73\u201375 (1990).","journal-title":"J. Graph Theory"},{"key":"22_CR15","doi-asserted-by":"crossref","unstructured":"M. Yannakakis, Node-and edge-deletion NP-complete problems, in \u201cProceedings, 10th ACM Sympos. on Theory of Comput. 1978,\u201d; pp. 253\u2013264.","DOI":"10.1145\/800133.804355"}],"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-60618-1_82.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:00:56Z","timestamp":1605646856000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60618-1_82"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540606185","9783540484875"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-60618-1_82","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}