{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T15:34:12Z","timestamp":1743089652840,"version":"3.40.3"},"publisher-location":"Cham","reference-count":12,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319559100"},{"type":"electronic","value":"9783319559117"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-55911-7_37","type":"book-chapter","created":{"date-parts":[[2017,3,20]],"date-time":"2017-03-20T14:23:37Z","timestamp":1490019817000},"page":"515-528","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On Complexity of Total Vertex Cover on Subcubic Graphs"],"prefix":"10.1007","author":[{"given":"Sheung-Hung","family":"Poon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wei-Lin","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,3,21]]},"reference":[{"issue":"1\u20132","key":"37_CR1","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","volume":"237","author":"P Alimonti","year":"2000","unstructured":"Alimonti, P., Kann, V.: Some APX-completeness results for cubic graphs. Theoret. Comput. Sci. 237(1\u20132), 123\u2013134 (2000)","journal-title":"Theoret. Comput. Sci."},{"key":"37_CR2","doi-asserted-by":"crossref","unstructured":"Crescenzi, P.: A short guide to approximation preserving reductions. In: Proceedings of the 12th Annual IEEE Conference on Computational Complexity, pp. 262\u2013273 (1997)","DOI":"10.1109\/CCC.1997.612321"},{"key":"37_CR3","doi-asserted-by":"crossref","unstructured":"de Berg, M., Khosravi, A.: Optimal binary space partitions in the plane. In: Proceedings of the 16th International Conference on Computing and Combinatorics, pp. 329\u2013343 (2010)","DOI":"10.1007\/978-3-642-14031-0_25"},{"issue":"2","key":"37_CR4","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/j.jda.2008.09.007","volume":"7","author":"H Fernau","year":"2009","unstructured":"Fernau, H., Manlove, D.F.: Vertex and edge covers with clustering properties: complexity and algorithms. J. Discrete Algorithms 7(2), 149\u2013167 (2009)","journal-title":"J. Discrete Algorithms"},{"issue":"4","key":"37_CR5","doi-asserted-by":"crossref","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"MR Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: The rectilinear steiner tree problem is NP-complete. SIAM J. Appl. Math. 32(4), 826\u2013834 (1977)","journal-title":"SIAM J. Appl. Math."},{"key":"37_CR6","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1990)"},{"key":"37_CR7","doi-asserted-by":"crossref","unstructured":"Gross, J.L., Yellen, J.: Graph Theory and Its Applications. CRC Press, Boca Raton (2005)","DOI":"10.1201\/9781420057140"},{"key":"37_CR8","doi-asserted-by":"crossref","unstructured":"Hopcroft, J.E., Karp, R.M.: A $$n^{5\/2}$$ algorithm for maximum matchings in bipartite. In: Proceedings of 12th Annual IEEE Symposium on Switching and Automata Theory, pp. 225\u2013231 (1971)","DOI":"10.1109\/SWAT.1971.1"},{"key":"37_CR9","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Proceedings of a Symposium on the Complexity of Computer Computations, pp. 85\u2013103 (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"37_CR10","unstructured":"K\u00f6nig, D.: Vgr\u00e1fok \u00e9s m\u00e1trixok. Matematikai \u00e9s Fizikai Lapok 38, 116\u2013119 (1931)"},{"issue":"2","key":"37_CR11","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/0166-218X(92)90041-8","volume":"35","author":"OJ Murphy","year":"1992","unstructured":"Murphy, O.J.: Computing independent sets in graphs with large girth. Discrete Appl. Math. 35(2), 167\u2013170 (1992)","journal-title":"Discrete Appl. Math."},{"key":"37_CR12","unstructured":"Uehara, R.: NP-complete problems on a 3-connected cubic planar graph and their applications. Technical Report TWCU-M-0004, Tokyo Woman\u2019s Christian University (1996)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-55911-7_37","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,22]],"date-time":"2023-08-22T18:42:49Z","timestamp":1692729769000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-55911-7_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319559100","9783319559117"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-55911-7_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}