{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T15:22:30Z","timestamp":1768317750645,"version":"3.49.0"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2019,3,19]],"date-time":"2019-03-19T00:00:00Z","timestamp":1552953600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11071005"],"award-info":[{"award-number":["11071005"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2019,8]]},"DOI":"10.1007\/s10878-019-00403-3","type":"journal-article","created":{"date-parts":[[2019,3,19]],"date-time":"2019-03-19T06:07:08Z","timestamp":1552975628000},"page":"635-645","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["The connected vertex cover problem in k-regular graphs"],"prefix":"10.1007","volume":"38","author":[{"given":"Yuchao","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wei","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zishen","family":"Yang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,3,19]]},"reference":[{"key":"403_CR1","doi-asserted-by":"publisher","first-page":"2581","DOI":"10.1016\/j.tcs.2010.03.021","volume":"411","author":"J Cardinal","year":"2010","unstructured":"Cardinal J, Levy E (2010) Connected vertex covers in dense graphs. Theor Comput Sci 411:2581\u20132590","journal-title":"Theor Comput Sci"},{"key":"403_CR2","first-page":"43","volume-title":"Graph theory","author":"R Diestel","year":"2000","unstructured":"Diestel R (2000) Graph theory. Springer, New York, pp 43\u201344"},{"key":"403_CR3","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/j.jda.2009.01.005","volume":"8","author":"B Esc","year":"2010","unstructured":"Esc B, Gou L, Mon J (2010) Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs. J Discrete Algorithm 8:36\u201349","journal-title":"J Discrete Algorithm"},{"key":"403_CR4","first-page":"69","volume":"7","author":"H Fernau","year":"2006","unstructured":"Fernau H, Manlove D (2006) Vertex and edge covers with clustering properties: complexity and algorithms. Algorithms Complex Durham 7:69\u201384","journal-title":"Algorithms Complex Durham"},{"key":"403_CR5","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/j.ipl.2004.01.011","volume":"90","author":"T Fujito","year":"2004","unstructured":"Fujito T, Doi T (2004) A 2-approximation NC algorithm for connected vertex cover and tree cover. Inf Process Lett 90:59\u201363","journal-title":"Inf Process Lett"},{"key":"403_CR6","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"MR Garey","year":"1977","unstructured":"Garey MR, Johnson DS (1977) The rectilinear Steiner tree problem is NP-complete. SIAM J Appl Math 32:826\u2013834","journal-title":"SIAM J Appl Math"},{"key":"403_CR7","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman, London"},{"key":"403_CR8","first-page":"36","volume-title":"Parameterized complexity of generalized vertex cover problems, algorithms and data structures","author":"J Guo","year":"2005","unstructured":"Guo J, Niedermeier R, Wernicke S (2005) Parameterized complexity of generalized vertex cover problems, algorithms and data structures, vol 3608. Springer, Berlin, pp 36\u201348"},{"key":"403_CR9","unstructured":"Karpinski M, Zelikovsky A (1997) Approximating dense cases of covering problems. In: Pardalos P, Du D (eds) Proceedings of the DIMACS workshop on network design: connectivity and facilities location. DIMACS series in discrete mathematics and theoretical computer science vol 40, pp 169C178"},{"key":"403_CR10","first-page":"107","volume":"301","author":"Y Li","year":"2017","unstructured":"Li Y, Yang Z, Wang W (2017) Complexity and algorithms for the connected vertex cover problem in 4-regular graphs. Appl Math Comput 301:107\u2013114","journal-title":"Appl Math Comput"},{"key":"403_CR11","first-page":"265","volume-title":"Enumerate and expand: new runtime bounds for vertex cover variants, computing and combinatorics","author":"D M\u00f6lle","year":"2006","unstructured":"M\u00f6lle D, Richter S, Rossmanith P (2006) Enumerate and expand: new runtime bounds for vertex cover variants, computing and combinatorics, vol 4112. Springer, Berlin, pp 265\u2013273"},{"key":"403_CR12","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/s00224-007-9089-3","volume":"43","author":"D M\u00f6lle","year":"2008","unstructured":"M\u00f6lle D, Richter S, Rossmanith P (2008) Enumerate and expand: improved algorithms for connected vertex cover and tree cover. Theor Comput Syst 43:234\u2013253","journal-title":"Theor Comput Syst"},{"key":"403_CR13","unstructured":"Moser H (2005) Exact algorithms for generalizations of vertex cover, Masters thesis, Fakult\u00e4t f\u00fcr Mathematik und Informatik, Friedrich-Schiller-Universit\u00e4t Jena"},{"key":"403_CR14","first-page":"51","volume":"2","author":"PK Priyadarsini","year":"2008","unstructured":"Priyadarsini PK, Hemalatha T (2008) Connected vertex cover in 2-connected planar graph with maximum degree 4 is NP-complete. Int J Math Phys Eng Sci 2:51\u201354","journal-title":"Int J Math Phys Eng Sci"},{"issue":"5","key":"403_CR15","doi-asserted-by":"publisher","first-page":"233C237","DOI":"10.1016\/0020-0190(82)90022-9","volume":"14","author":"CD Savage","year":"1982","unstructured":"Savage CD (1982) Depth-first search and the vertex cover problem. Inf Process Lett 14(5):233C237","journal-title":"Inf Process Lett"},{"key":"403_CR16","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1016\/0012-365X(88)90226-9","volume":"72","author":"S Ueno","year":"1988","unstructured":"Ueno S, Kajitani Y, Gotoh S (1988) On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three. Discrete Math 72:355\u2013360","journal-title":"Discrete Math"},{"key":"403_CR17","unstructured":"Wanatabe T, Kajita S, Onaga K (1991) Vertex covers and connected vertex covers in 3-connected graphs. In: Circuits and systems ieee international sympoisum on, vol 2, pp 1017\u20131020"},{"key":"403_CR18","doi-asserted-by":"publisher","first-page":"5398","DOI":"10.1016\/j.tcs.2009.01.035","volume":"410","author":"Z Zhang","year":"2009","unstructured":"Zhang Z, Gao X, Wu W (2009) PTAS for connected vertex cover in unit disk graphs. Theor Comput Sci 410:5398\u20135402","journal-title":"Theor Comput Sci"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-019-00403-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-019-00403-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-019-00403-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,18]],"date-time":"2020-03-18T00:05:18Z","timestamp":1584489918000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-019-00403-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,19]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,8]]}},"alternative-id":["403"],"URL":"https:\/\/doi.org\/10.1007\/s10878-019-00403-3","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,3,19]]},"assertion":[{"value":"19 March 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}