{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:26:49Z","timestamp":1759638409334},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,2,12]],"date-time":"2016-02-12T00:00:00Z","timestamp":1455235200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"National Natural Science Founda- tion of China","award":["11201021"],"award-info":[{"award-number":["11201021"]}]},{"DOI":"10.13039\/501100010026","name":"Beijing Higher Education Young Elite Teacher Project","doi-asserted-by":"crossref","award":["YETP0517"],"award-info":[{"award-number":["YETP0517"]}],"id":[{"id":"10.13039\/501100010026","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2017,8]]},"DOI":"10.1007\/s10878-016-9999-6","type":"journal-article","created":{"date-parts":[[2016,2,12]],"date-time":"2016-02-12T09:49:04Z","timestamp":1455270544000},"page":"414-425","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["On the vertex cover $$P_3$$ P 3 problem parameterized by treewidth"],"prefix":"10.1007","volume":"34","author":[{"given":"Jianhua","family":"Tu","sequence":"first","affiliation":[]},{"given":"Lidong","family":"Wu","sequence":"additional","affiliation":[]},{"given":"Jing","family":"Yuan","sequence":"additional","affiliation":[]},{"given":"Lei","family":"Cui","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,2,12]]},"reference":[{"key":"9999_CR1","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1016\/j.jalgor.2004.03.005","volume":"52","author":"J Alber","year":"2004","unstructured":"Alber J, Fernau H, Niedermeier R (2004) Parameteized complexity: exponential speed-up for planar graph problems. J Algorithms 52:26\u201356","journal-title":"J Algorithms"},{"key":"9999_CR2","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund A, Husfeldt T, Kaski P, Koivisto M (2007) Fourier meets M\u00f6bius: fast subset convolution. In: Proceedings of the 39th annual symposium on theory of computing, STOC 2007, pp 67\u201374","DOI":"10.1145\/1250790.1250801"},{"key":"9999_CR3","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender HL (1996) A linear time algorithm for finding tree-decompostions of small treewidth. SIAM J Comput 25:1305\u20131317","journal-title":"SIAM J Comput"},{"key":"9999_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"HL Bodlaender","year":"1998","unstructured":"Bodlaender HL (1998) A partial $$k$$ k -arboretum of graphs with bounded treewidth. Theor Comput Sci 209:1\u201345","journal-title":"Theor Comput Sci"},{"key":"9999_CR5","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/j.ic.2009.03.008","volume":"208","author":"HL Bodlaender","year":"2010","unstructured":"Bodlaender HL, Koster AMCA (2010) Treewidth computations I. Upper bounds. Inf Comput 208:259\u2013275","journal-title":"Inf Comput"},{"key":"9999_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-349-03521-2","volume-title":"Graph theory with applications","author":"JA Bondy","year":"1976","unstructured":"Bondy JA, Murty USR (1976) Graph theory with applications. Elsevier, New York"},{"key":"9999_CR7","doi-asserted-by":"crossref","first-page":"1943","DOI":"10.1016\/j.dam.2013.02.024","volume":"161","author":"B Bre\u0161ar","year":"2013","unstructured":"Bre\u0161ar B, Jakovac M, Katreni\u010d J, Semani\u0161in G, Taranenko A (2013) On the vertex $$k$$ k -path cover. Discrete Appl Math 161:1943\u20131949","journal-title":"Discrete Appl Math"},{"key":"9999_CR8","doi-asserted-by":"crossref","first-page":"1189","DOI":"10.1016\/j.dam.2011.04.008","volume":"159","author":"B Bre\u0161ar","year":"2011","unstructured":"Bre\u0161ar B, Kardo\u0161 F, Katreni\u010d J, Semani\u0161in G (2011) Minimum $$k$$ k -path vertex cover. Discrete Appl Math 159:1189\u20131195","journal-title":"Discrete Appl Math"},{"key":"9999_CR9","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/j.dam.2014.05.042","volume":"177","author":"B Bre\u0161ar","year":"2014","unstructured":"Bre\u0161ar B, Krivo\u0161-Bellu\u0161 R, Semani\u0161in G, \u0160parl P (2014) On the weighted $$k$$ k -path vertex cover problem. Discrete Appl Math 177:14\u201318","journal-title":"Discrete Appl Math"},{"key":"9999_CR10","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0020-0190(96)00050-6","volume":"58","author":"LZ Cai","year":"1996","unstructured":"Cai LZ (1996) Fixed-parameter tractability of graph modification problems for hereditary properties. Infrom Process Lett 58:171\u2013176","journal-title":"Infrom Process Lett"},{"key":"9999_CR11","unstructured":"Chang MS, Chen LH, Hung LJ, Liu YZ, Rossmanith P, Sikdar S (2014) An $$O^*(1.4658^n)$$ O \u2217 ( 1 . 4658 n ) -time exact algorithm for the maximum bounded-degree-1 set problem. In: Proceedings of the 31st workshop on combinatorial mathematics and computation theory, pp 9\u201318"},{"key":"9999_CR12","doi-asserted-by":"crossref","unstructured":"Chen J, Fernau H, Shaw P, Wang JX, Yang ZB (2012) Kernels for packing and covering problems (extended abstract). In: Hirsch E, Kuznetsov S, Pin Jr, Vereshchagin N (eds) Proceedings of FAW-AAIM 2012, Lecture Notes in Computer Science, vol 7285, pp 199\u2013211, Springer International Publishing","DOI":"10.1007\/978-3-642-29700-7_19"},{"key":"9999_CR13","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle B (1990) The monadic second-order logic of graphs, I: recognizable sets of finite graphs. Inf Comput 85:12\u201375","journal-title":"Inf Comput"},{"key":"9999_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan M, Fomin FV, Kowalik L, Lokshtanov D, Mark D, Pilipczuk M, Pilipczuk M, Saurabh S (2015) Parameterized algorithms. Springer, Heidelberg"},{"key":"9999_CR15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1944857.1944860","volume":"2","author":"MR Fellows","year":"2011","unstructured":"Fellows MR, Guo J, Moser H, Niedermeier R (2011) A complexity dichotomy for finding disjoint solutions of vertex deletion problems. ACM Trans Comput Theory 2:1\u201323","journal-title":"ACM Trans Comput Theory"},{"key":"9999_CR16","volume-title":"Parameterized complexity theory, texts in theoretical computer science","author":"J Flum","year":"2006","unstructured":"Flum J, Grohe M (2006) Parameterized complexity theory, texts in theoretical computer science. Springer, Berlin"},{"key":"9999_CR17","doi-asserted-by":"crossref","unstructured":"Katreni\u010d J (2016) A faster FPT algorithm for 3-path vertex cover. Inform Process Lett 116(4):273\u2013278","DOI":"10.1016\/j.ipl.2015.12.002"},{"key":"9999_CR18","doi-asserted-by":"crossref","first-page":"7009","DOI":"10.1016\/j.tcs.2011.09.009","volume":"412","author":"F Kardo\u0161","year":"2011","unstructured":"Kardo\u0161 F, Katreni\u010d J, Schiermeyer I (2011) On computing the minimum 3-path vertex cover and dissociation number of graphs. Theor Comput Sci 412:7009\u20137017","journal-title":"Theor Comput Sci"},{"key":"9999_CR19","volume-title":"Algorithm design","author":"J Kleinberg","year":"2005","unstructured":"Kleinberg J, Tardos E (2005) Algorithm design. Addison-Wesley, Boston"},{"key":"9999_CR20","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"JM Lewis","year":"1980","unstructured":"Lewis JM, Yannakakis M (1980) The node-deletion problem for hereditary properties is NP-complete. J Comput Syst Sci 20:219\u2013230","journal-title":"J Comput Syst Sci"},{"key":"9999_CR21","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/s10878-011-9391-5","volume":"24","author":"H Moser","year":"2012","unstructured":"Moser H, Niedermeier R, Sorge M (2012) Exact combinatorial algorithms and experiments for finding maximum $$k$$ k -plexes. J Comb Optim 24:347\u2013373","journal-title":"J Comb Optim"},{"key":"9999_CR22","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to fixed-parameter algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier R (2006) Invitation to fixed-parameter algorithms. Oxford University Press, Oxford"},{"key":"9999_CR23","doi-asserted-by":"crossref","unstructured":"Novotn\u00fd M (2010) Design and analysis of a generalized canvas protocol. In: Proceedings of WISTP 2010, In: LNCS, vol 6033, Springer-Verlag, pp 106\u2013121","DOI":"10.1007\/978-3-642-12368-9_8"},{"key":"9999_CR24","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N Robertson","year":"1986","unstructured":"Robertson N, Seymour PD (1986) Graph minors, II. Algorithmic aspects of tree-width. J Algorithms 7:309\u2013322","journal-title":"J Algorithms"},{"key":"9999_CR25","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1016\/j.ipl.2014.06.018","volume":"115","author":"JH Tu","year":"2015","unstructured":"Tu JH (2015) A fixed-parameter algorithm for the vertex cover $$P_3$$ P 3 problem. Inf Process Lett 115:96\u201399","journal-title":"Inf Process Lett"},{"key":"9999_CR26","doi-asserted-by":"crossref","first-page":"7044","DOI":"10.1016\/j.tcs.2011.09.013","volume":"412","author":"JH Tu","year":"2011","unstructured":"Tu JH, Zhou WL (2011) A primal-dual approximation algorithm for the vertex cover $$P_3$$ P 3 problem. Theor Comput Sci 412:7044\u20137048","journal-title":"Theor Comput Sci"},{"key":"9999_CR27","doi-asserted-by":"crossref","first-page":"683","DOI":"10.1016\/j.ipl.2011.04.009","volume":"111","author":"JH Tu","year":"2011","unstructured":"Tu JH, Zhou WL (2011) A factor 2 approximation algorithm for the vertex cover $$P_3$$ P 3 problem. Inf Process Lett 111:683\u2013686","journal-title":"Inf Process Lett"},{"key":"9999_CR28","first-page":"469","volume":"2015","author":"BY Wu","year":"2015","unstructured":"Wu BY (2015) A measure and conquer approach for the parameterized bounded degree-one vertex deletion. COCOON 2015:469\u2013480","journal-title":"COCOON"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-016-9999-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-016-9999-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-016-9999-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-016-9999-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,15]],"date-time":"2020-09-15T09:33:47Z","timestamp":1600162427000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-016-9999-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,12]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,8]]}},"alternative-id":["9999"],"URL":"https:\/\/doi.org\/10.1007\/s10878-016-9999-6","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,2,12]]}}}