{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T22:35:43Z","timestamp":1777502143880,"version":"3.51.4"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2018,1,13]],"date-time":"2018-01-13T00:00:00Z","timestamp":1515801600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2018,11]]},"DOI":"10.1007\/s00224-017-9837-y","type":"journal-article","created":{"date-parts":[[2018,1,12]],"date-time":"2018-01-12T23:14:56Z","timestamp":1515798896000},"page":"1690-1714","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Revisiting Connected Vertex Cover: FPT Algorithms and Lossy Kernels"],"prefix":"10.1007","volume":"62","author":[{"given":"R.","family":"Krithika","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Diptapriyo","family":"Majumdar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,1,13]]},"reference":[{"issue":"1-2","key":"9837_CR1","doi-asserted-by":"publisher","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. Theor. Comput. Sci. 237(1-2), 123\u2013134 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"9837_CR2","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.ic.2014.12.008","volume":"243","author":"HL Bodlaender","year":"2015","unstructured":"Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by Treewidth. Inf. Comput. 243, 86\u2013111 (2015)","journal-title":"Inf. Comput."},{"issue":"2","key":"9837_CR3","first-page":"263","volume":"63","author":"HL Bodlaender","year":"2013","unstructured":"Bodlaender, H.L., Jansen, B.M.P.: Vertex cover kernelization revisited: upper and lower bounds for a refined parameter. Theory Comput. Syst. 63(2), 263\u2013299 (2013)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"9837_CR4","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/120880240","volume":"28","author":"HL Bodlaender","year":"2014","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernelization lower bounds by cross-composition. SIAM J. Discret. Math. 28(1), 277\u2013305 (2014)","journal-title":"SIAM J. Discret. Math."},{"issue":"2","key":"9837_CR5","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/s00224-015-9631-7","volume":"58","author":"A Boral","year":"2016","unstructured":"Boral, A., Cygan, M., Kociumaka, T., Pilipczuk, M.: A fast branching algorithm for cluster vertex deletion. Theory Comput. Syst. 58(2), 357\u2013376 (2016)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"9837_CR6","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1006\/jagm.2001.1186","volume":"41","author":"J Chen","year":"2001","unstructured":"Chen, J., Kanj, I.A., Jia, W.: Vertex cover: further observations and further improvements. J. Algorithms 41(2), 280\u2013301 (2001)","journal-title":"J. Algorithms"},{"key":"9837_CR7","doi-asserted-by":"crossref","unstructured":"Cygan, M.: Deterministic Parameterized Connected Vertex Cover. In: Proceedings of the 13Th Scandinavian Workshop on Algorithm Theory (SWAT), pp 95\u2013106 (2012)","DOI":"10.1007\/978-3-642-31155-0_9"},{"issue":"3","key":"9837_CR8","doi-asserted-by":"publisher","first-page":"41:1","DOI":"10.1145\/2925416","volume":"12","author":"M Cygan","year":"2016","unstructured":"Cygan, M., Dell, H., Lokshtanov, D., Marx, D., Nederlof, J., Okamoto, Y., Paturi, R., Saurabh, S., Wahlstr\u00f6m, M.: On problems as hard as CNF-SAT. ACM Trans. Algorithms 12(3), 41:1\u201341:24 (2016)","journal-title":"ACM Trans. Algorithms"},{"key":"9837_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"issue":"5-6","key":"9837_CR10","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/j.ipl.2013.01.001","volume":"113","author":"M Cygan","year":"2013","unstructured":"Cygan, M., Pilipczuk, M.: Split vertex deletion meets vertex cover: new fixed-parameter and exact exponential-time algorithms. Inf. Process. Lett. 113(5-6), 179\u2013182 (2013)","journal-title":"Inf. Process. Lett."},{"key":"9837_CR11","volume-title":"Graph Theory, Graduate Text in Mathematics","author":"R Diestel","year":"2012","unstructured":"Diestel, R.: Graph Theory, Graduate Text in Mathematics. Springer, Berlin (2012)"},{"issue":"2","key":"9837_CR12","doi-asserted-by":"publisher","first-page":"13:1","DOI":"10.1145\/2650261","volume":"11","author":"M Dom","year":"2014","unstructured":"Dom, M., Lokshatanov, D., Saurabh, S.: Kernelization lower bounds through colors and IDs. ACM Trans. Algorithms 11(2), 13:1\u201313:20 (2014)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"9837_CR13","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/j.jda.2009.01.005","volume":"8","author":"B Escoffier","year":"2010","unstructured":"Escoffier, B., Gourv\u00e8s, L., Monno, J.: Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs. J. Discrete Algoritms 8(1), 36\u201349 (2010)","journal-title":"J. Discrete Algoritms"},{"key":"9837_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact Exponential Algorithms","author":"F Fomin","year":"2010","unstructured":"Fomin, F., Kratsch, D.: Exact Exponential Algorithms. Springer, Berlin (2010)"},{"key":"9837_CR15","volume-title":"Computer and Intractability: A Guide to the Theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computer and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman & Co., Bedford (1979)"},{"key":"9837_CR16","volume-title":"Algorithmic Graph Theory for Perfect Graphs","author":"MC Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory for Perfect Graphs. Springer, Berlin (2004)"},{"key":"9837_CR17","volume-title":"The Power of Data Reduction: Kernels for Fundamental Graph Problems","author":"BMP Jansen","year":"2013","unstructured":"Jansen, B.M.P.: The Power of Data Reduction: Kernels for Fundamental Graph Problems. PhD Thesis, Utrecht University, The Netherlands (2013)"},{"issue":"3","key":"9837_CR18","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1016\/j.ejc.2012.04.008","volume":"34","author":"BMP Jansen","year":"2013","unstructured":"Jansen, B.M.P., Fellows, M.R., Rosamond, F.A.: Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity. Eur. J. Comb. 34(3), 541\u2013566 (2013)","journal-title":"Eur. J. Comb."},{"key":"9837_CR19","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1016\/j.ic.2013.08.005","volume":"231","author":"BMP Jansen","year":"2013","unstructured":"Jansen, B.M.P., Kratsch, S.: Data reduction for coloring problems. Inf. Comput. 231, 70\u201388 (2013)","journal-title":"Inf. Comput."},{"issue":"4","key":"9837_CR20","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1109\/TST.2014.6867520","volume":"19","author":"BMP Jansen","year":"2014","unstructured":"Jansen, B.M.P., Raman, V., Vatshelle, M.: Parameter ecology for feedback vertex set. Tsinghua Sci. Technol. 19(4), 387\u2013409 (2014)","journal-title":"Tsinghua Sci. Technol."},{"issue":"2","key":"9837_CR21","doi-asserted-by":"publisher","first-page":"15:1","DOI":"10.1145\/2566616","volume":"11","author":"D Lokshtanov","year":"2014","unstructured":"Lokshtanov, D., Narayanaswamy, N.S., Raman, V., Ramanujan, M.S., Saurabh, S.: Faster parameterized algorithms using linear programming. ACM Trans. Algorithms 11(2), 15:1\u201315:31 (2014)","journal-title":"ACM Trans. Algorithms"},{"key":"9837_CR22","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Panolan, F., Ramanujan, M.S., Saurabh, S.: Lossy kernelization. In: Proceedings of the 49Th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp 224\u2013237 (2017)","DOI":"10.1145\/3055399.3055456"},{"key":"9837_CR23","unstructured":"Moser, H.: Exact Algorithms for Generalizations of Vertex Cover. Master\u2019s Thesis, Institut f\u00fcr Informatik, Friedrich-Schiller-Universit\u00e4t (2005)"},{"key":"9837_CR24","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.: On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three. Discret. Math. 72, 355\u2013360 (1988)","journal-title":"Discret. Math."},{"key":"9837_CR25","doi-asserted-by":"crossref","unstructured":"Wu, B.Y.: A measure and conquer Based approach for the parameterized hounded degree-one vertex deletion. In: Proceedings of the 21St International Computing and Combinatorics Conference (COCOON), pp 469\u2013480 (2015)","DOI":"10.1007\/978-3-319-21398-9_37"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9837-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9837-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9837-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,9]],"date-time":"2019-10-09T05:44:51Z","timestamp":1570599891000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9837-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,13]]},"references-count":25,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["9837"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9837-y","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1,13]]},"assertion":[{"value":"13 January 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}