{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,27]],"date-time":"2026-01-27T10:36:24Z","timestamp":1769510184944,"version":"3.49.0"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2022,9,30]],"date-time":"2022-09-30T00:00:00Z","timestamp":1664496000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,9,30]],"date-time":"2022-09-30T00:00:00Z","timestamp":1664496000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,12]]},"DOI":"10.1007\/s10878-022-00917-3","type":"journal-article","created":{"date-parts":[[2022,9,30]],"date-time":"2022-09-30T09:11:42Z","timestamp":1664529102000},"page":"3701-3710","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Faster deterministic algorithms for Co-path Packing and Co-path\/cycle Packing"],"prefix":"10.1007","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9763-3784","authenticated-orcid":false,"given":"Dekel","family":"Tsur","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,9,30]]},"reference":[{"key":"917_CR1","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/j.jcss.2017.07.008","volume":"92","author":"A Agrawal","year":"2018","unstructured":"Agrawal A, Saurabh S, Sharma R, Zehavi M (2018a) Kernels for deletion to classes of acyclic digraphs. J Comput Syst Sci 92:9\u201321","journal-title":"J Comput Syst Sci"},{"key":"917_CR2","doi-asserted-by":"crossref","unstructured":"Agrawal A, Saurabh S, Sharma R, Zehavi M (2018b) Parameterised algorithms for deletion to classes of DAGs. Theory Comput Syst 1\u201330","DOI":"10.1007\/s00224-018-9852-7"},{"key":"917_CR3","unstructured":"Aoike Y, Gima T, Hanaka T, Kiyomi M, Kobayashi Y, Kobayashi Y, Kurita K, Otachi Y (2020) An improved deterministic parameterized algorithm for cactus vertex deletion. arXiv preprint arXiv:2012.04910"},{"issue":"1\u20132","key":"917_CR4","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.dam.2011.08.013","volume":"160","author":"N Betzler","year":"2012","unstructured":"Betzler N, Bredereck R, Niedermeier R, Uhlmann J (2012) On bounded-degree vertex deletion parameterized by treewidth. Discret Appl Math 160(1\u20132):53\u201360","journal-title":"Discret Appl Math"},{"key":"917_CR5","doi-asserted-by":"crossref","unstructured":"Bonnet \u00c9, Brettell N, Kwon O-j, Marx D (2016) Parameterized vertex deletion problems for hereditary graph classes with a block property. In: Proceedings of 42nd workshop on graph-theoretic concepts in computer science (WG), pp 233\u2013244","DOI":"10.1007\/978-3-662-53536-3_20"},{"key":"917_CR6","unstructured":"\u010cerven\u1ef3 R, Such\u1ef3 O (2021) Generating faster algorithms for d-path vertex cover. arXiv preprint arXiv:2111.05896"},{"key":"917_CR7","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.disopt.2015.11.003","volume":"19","author":"M-S Chang","year":"2016","unstructured":"Chang M-S, Chen L-H, Hung L-J, Rossmanith P, Su P-C (2016) Fixed-parameter algorithms for vertex cover $$P_3$$. Discrete Optim 19:12\u201322","journal-title":"Discrete Optim"},{"key":"917_CR8","doi-asserted-by":"crossref","unstructured":"Chen Z-Z, Fellows M, Fu B, Jiang H, Liu Y, Wang L, Zhu B (2010) A linear kernel for co-path\/cycle packing. In: Proceedings of 6th conference on algorithmic applications in management (AAIM), pp 90\u2013102","DOI":"10.1007\/978-3-642-14355-7_10"},{"issue":"1","key":"917_CR9","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1007\/s00453-011-9578-2","volume":"64","author":"M Cygan","year":"2012","unstructured":"Cygan M, Pilipczuk M, Pilipczuk M, Wojtaszczyk JO (2012) An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion. Algorithmica 64(1):170\u2013188","journal-title":"Algorithmica"},{"issue":"6","key":"917_CR10","doi-asserted-by":"publisher","first-page":"1141","DOI":"10.1016\/j.jcss.2010.12.001","volume":"77","author":"MR Fellows","year":"2011","unstructured":"Fellows MR, Guo J, Moser H, Niedermeier R (2011) A generalization of Nemhauser and Trotter\u2019s local optimization theorem. J Comput Syst Sci 77(6):1141\u20131158","journal-title":"J Comput Syst Sci"},{"issue":"1","key":"917_CR11","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s10878-013-9691-z","volume":"29","author":"Q Feng","year":"2015","unstructured":"Feng Q, Wang J, Li S, Chen J (2015) Randomized parameterized algorithms for $$P_2$$-packing and co-path packing problems. J Comb Optim 29(1):125\u2013140","journal-title":"J Comb Optim"},{"issue":"1","key":"917_CR12","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/s00453-020-00758-8","volume":"83","author":"R Ganian","year":"2021","unstructured":"Ganian R, Klute F, Ordyniak S (2021) On structural parameterizations of the bounded-degree vertex deletion problem. Algorithmica 83(1):297\u2013336","journal-title":"Algorithmica"},{"issue":"4","key":"917_CR13","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/j.ipl.2015.12.002","volume":"116","author":"J Katreni\u010d","year":"2016","unstructured":"Katreni\u010d J (2016) A faster FPT algorithm for 3-path vertex cover. Inf Process Lett 116(4):273\u2013278","journal-title":"Inf Process Lett"},{"issue":"1","key":"917_CR14","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/s00453-017-0317-1","volume":"79","author":"S Kolay","year":"2017","unstructured":"Kolay S, Lokshtanov D, Panolan F, Saurabh S (2017) Quick but odd growth of cacti. Algorithmica 79(1):271\u2013290","journal-title":"Algorithmica"},{"issue":"38\u201340","key":"917_CR15","doi-asserted-by":"publisher","first-page":"3640","DOI":"10.1016\/j.tcs.2009.04.021","volume":"410","author":"C Komusiewicz","year":"2009","unstructured":"Komusiewicz C, H\u00fcffner F, Moser H, Niedermeier R (2009) Isolation concepts for efficiently enumerating dense subgraphs. Theoret Comput Sci 410(38\u201340):3640\u20133654","journal-title":"Theoret Comput Sci"},{"key":"917_CR16","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1016\/j.disopt.2017.02.002","volume":"25","author":"M Mnich","year":"2017","unstructured":"Mnich M, van Leeuwen EJ (2017) Polynomial kernels for deletion to classes of acyclic digraphs. Discrete Optim 25:48\u201376","journal-title":"Discrete Optim"},{"issue":"1\u20133","key":"917_CR17","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/j.dam.2005.02.029","volume":"152","author":"N Nishimura","year":"2005","unstructured":"Nishimura N, Ragde P, Thilikos DM (2005) Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover. Discrete Appl Math 152(1\u20133):229\u2013245","journal-title":"Discrete Appl Math"},{"key":"917_CR18","doi-asserted-by":"crossref","unstructured":"Philip G, Raman V, Villanger Y (2010) A quartic kernel for pathwidth-one vertex deletion. In: Proceedings of 36th international workshop on graph-theoretic concepts in computer science (WG), pp 196\u2013207","DOI":"10.1007\/978-3-642-16926-7_19"},{"issue":"1","key":"917_CR19","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1080\/0022250X.1978.9989883","volume":"6","author":"SB Seidman","year":"1978","unstructured":"Seidman SB, Foster BL (1978) A graph-theoretic generalization of the clique concept. J Math Sociol 6(1):139\u2013154","journal-title":"J Math Sociol"},{"key":"917_CR20","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1016\/j.ipl.2019.03.009","volume":"147","author":"D Tsur","year":"2019","unstructured":"Tsur D (2019) Faster parameterized algorithm for pumpkin vertex deletion set. Inf Process Lett 147:74\u201376","journal-title":"Inf Process Lett"},{"key":"917_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2019.03.013","volume":"783","author":"D Tsur","year":"2019","unstructured":"Tsur D (2019) Parameterized algorithm for 3-path vertex cover. Theoret Comput Sci 783:1\u20138","journal-title":"Theoret Comput Sci"},{"key":"917_CR22","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.tcs.2022.04.001","volume":"921","author":"D Tsur","year":"2022","unstructured":"Tsur D (2022) Faster algorithm for pathwidth one vertex deletion. Theoret Comput Sci 921:63\u201374","journal-title":"Theoret Comput Sci"},{"issue":"2","key":"917_CR23","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/j.ipl.2014.06.018","volume":"115","author":"J Tu","year":"2015","unstructured":"Tu J (2015) A fixed-parameter algorithm for the vertex cover $$P_3$$ problem. Inf Process Lett 115(2):96\u201399","journal-title":"Inf Process Lett"},{"key":"917_CR24","doi-asserted-by":"crossref","unstructured":"Wu BY (2015) A measure and conquer approach for the parameterized bounded degree-one vertex deletion. In: Proceedings of 21st international computing and combinatorics conference (COCOON), pp 469\u2013480","DOI":"10.1007\/978-3-319-21398-9_37"},{"key":"917_CR25","doi-asserted-by":"crossref","unstructured":"Xiao M (2016) A parameterized algorithm for bounded-degree vertex deletion. In: Proceedings of 22nd computing and combinatorics conference (COCOON), pp 79\u201391","DOI":"10.1007\/978-3-319-42634-1_7"},{"key":"917_CR26","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.jcss.2016.08.003","volume":"84","author":"M Xiao","year":"2017","unstructured":"Xiao M (2017) On a generalization of Nemhauser and Trotter\u2019s local optimization theorem. J Comput Syst Sci 84:97\u2013106","journal-title":"J Comput Syst Sci"},{"key":"917_CR27","doi-asserted-by":"crossref","unstructured":"Xiao M, Kou S (2017) Kernelization and parameterized algorithms for 3-path vertex cover. In: Proceedings of 14th international conference on theory and applications of models of computation (TAMC), pp 654\u2013668","DOI":"10.1007\/978-3-319-55911-7_47"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00917-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-022-00917-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00917-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,29]],"date-time":"2022-10-29T09:40:46Z","timestamp":1667036446000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-022-00917-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,30]]},"references-count":27,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["917"],"URL":"https:\/\/doi.org\/10.1007\/s10878-022-00917-3","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,30]]},"assertion":[{"value":"19 September 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 September 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}