{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:07:56Z","timestamp":1725455276865},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540605737"},{"type":"electronic","value":"9783540477662"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/bfb0015449","type":"book-chapter","created":{"date-parts":[[2005,11,13]],"date-time":"2005-11-13T01:50:06Z","timestamp":1131846606000},"page":"428-437","source":"Crossref","is-referenced-by-count":3,"title":["NC algorithms for partitioning sparse graphs into induced forests with an application"],"prefix":"10.1007","author":[{"given":"Zhi-Zhong","family":"Chen","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,9]]},"reference":[{"key":"48_CR1","doi-asserted-by":"crossref","unstructured":"N. Alon, P. Seymour, and R. Thomas, A separator theorem for graphs without an excluded minor and its applications, in \u201cProceedings, 22nd ACM Sympos. on Theory of Comput. 1990,\u201d pp. 293\u2013299.","DOI":"10.1145\/100216.100254"},{"key":"48_CR2","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 (1985) 249\u2013267.","journal-title":"Theoret. Comput. Sci."},{"key":"48_CR3","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 (1994) 153\u2013180.","journal-title":"J. ACM"},{"key":"48_CR4","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 (1968) 169\u2013175.","journal-title":"Israel J. Math."},{"key":"48_CR5","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 (1969) 612\u2013616.","journal-title":"J. London Math. Soc."},{"key":"48_CR6","unstructured":"Z.-Z. Chen and X. He, Parallel complexity of partitioning a planar graph into vertex-induced forests, to appear in Discrete Applied Mathematics; A preliminary version was presented at 21st International Workshop on Graph-Theoretic Concepts in Computer Science, Aachen, Germany, June 20\u201322, 1995."},{"key":"48_CR7","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1007\/BF01361708","volume":"153","author":"G.A. Dirac","year":"1964","unstructured":"G.A. Dirac, Homomorphism theorems for graphs, Math. Ann. 153 (1964) 69\u201380.","journal-title":"Math. Ann."},{"key":"48_CR8","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M. Garey","year":"1979","unstructured":"M. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, (Freeman, San Francisco, 1979)."},{"key":"48_CR9","doi-asserted-by":"crossref","unstructured":"A. K\u00e9zdy and P. McGuinness, Sequential and parallel algorithms to find a K 5 minor, in \u201cProceedings, 3rd ACM-SIAM Sympos. on Discrete Algorithms. 1992,\u201d pp. 345\u2013356.","DOI":"10.21236\/ADA232901"},{"key":"48_CR10","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R.J. Lipton","year":"1980","unstructured":"R.J. Lipton and R.E. Tarjan, Applications of a planar separator theorem, SIAM J. Comput. 9 (1980) 615\u2013627.","journal-title":"SIAM J. Comput."},{"key":"48_CR11","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","Algorithms and Computations"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0015449","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,10]],"date-time":"2020-04-10T16:49:37Z","timestamp":1586537377000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0015449"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540605737","9783540477662"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/bfb0015449","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}