{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T11:50:51Z","timestamp":1770465051006,"version":"3.49.0"},"publisher-location":"Cham","reference-count":41,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031433795","type":"print"},{"value":"9783031433801","type":"electronic"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-43380-1_12","type":"book-chapter","created":{"date-parts":[[2023,9,22]],"date-time":"2023-09-22T20:29:12Z","timestamp":1695414552000},"page":"157-171","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Generating Faster Algorithms for\u00a0d-Path Vertex Cover"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4528-9525","authenticated-orcid":false,"given":"Radovan","family":"\u010cerven\u00fd","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7236-8336","authenticated-orcid":false,"given":"Ond\u0159ej","family":"Such\u00fd","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,9,23]]},"reference":[{"issue":"3","key":"12_CR1","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/S0020-0190(97)00213-5","volume":"65","author":"R Balasubramanian","year":"1998","unstructured":"Balasubramanian, R., Fellows, M.R., Raman, V.: An improved fixed-parameter algorithm for vertex cover. Inf. Process. Lett. 65(3), 163\u2013168 (1998). https:\/\/doi.org\/10.1016\/S0020-0190(97)00213-5","journal-title":"Inf. Process. Lett."},{"issue":"12","key":"12_CR2","doi-asserted-by":"publisher","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.: Minimum $$k$$-path vertex cover. Discret. Appl. Math. 159(12), 1189\u20131195 (2011). https:\/\/doi.org\/10.1016\/j.dam.2011.04.008","journal-title":"Discret. Appl. Math."},{"key":"12_CR3","doi-asserted-by":"publisher","unstructured":"Buss, J.F., Goldsmith, J.: Nondeterminism within P. SIAM J. Comput. 22(3), 560\u2013572 (1993). https:\/\/doi.org\/10.1137\/0222038","DOI":"10.1137\/0222038"},{"key":"12_CR4","doi-asserted-by":"publisher","unstructured":"\u010cerven\u00fd, R., Such\u00fd, O.: Faster FPT algorithm for 5-path vertex cover. In: Rossmanith, P., Heggernes, P., Katoen, J. (eds.) 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26\u201330, 2019, Aachen, Germany. LIPIcs, vol. 138, pp. 32:1\u201332:13. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2019.32","DOI":"10.4230\/LIPIcs.MFCS.2019.32"},{"key":"12_CR5","unstructured":"\u010cerven\u00fd, R., Such\u00fd, O.: Generating faster algorithms for $$d$$-path vertex cover (2021). arxiv.org\/abs\/2111.05896"},{"issue":"3","key":"12_CR6","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/j.ipl.2004.10.003","volume":"93","author":"LS Chandran","year":"2005","unstructured":"Chandran, L.S., Grandoni, F.: Refined memorization for vertex cover. Inf. Process. Lett. 93(3), 123\u2013131 (2005). https:\/\/doi.org\/10.1016\/j.ipl.2004.10.003","journal-title":"Inf. Process. Lett."},{"key":"12_CR7","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1016\/j.dam.2018.05.032","volume":"251","author":"M Chang","year":"2018","unstructured":"Chang, M., Chen, L., Hung, L., Liu, Y., Rossmanith, P., Sikdar, S.: Moderately exponential time algorithms for the maximum bounded-degree-1 set problem. Discret. Appl. Math. 251, 114\u2013125 (2018). https:\/\/doi.org\/10.1016\/j.dam.2018.05.032","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"12_CR8","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). https:\/\/doi.org\/10.1006\/jagm.2001.1186","journal-title":"J. Algorithms"},{"issue":"4","key":"12_CR9","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s00453-004-1145-7","volume":"43","author":"J Chen","year":"2005","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Labeled search trees and amortized analysis: improved upper bounds for NP-hard problems. Algorithmica 43(4), 245\u2013273 (2005). https:\/\/doi.org\/10.1007\/s00453-004-1145-7","journal-title":"Algorithmica"},{"issue":"40\u201342","key":"12_CR10","doi-asserted-by":"publisher","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","volume":"411","author":"J Chen","year":"2010","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theor. Comput. Sci. 411(40\u201342), 3736\u20133756 (2010). https:\/\/doi.org\/10.1016\/j.tcs.2010.06.026","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"12_CR11","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1002\/1097-0037(200007)35:4<253::AID-NET3>3.0.CO;2-K","volume":"35","author":"J Chen","year":"2000","unstructured":"Chen, J., Liu, L., Jia, W.: Improvement on vertex cover for low-degree graphs. Networks 35(4), 253\u2013259 (2000)","journal-title":"Networks"},{"key":"12_CR12","doi-asserted-by":"publisher","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3","DOI":"10.1007\/978-3-319-21275-3"},{"key":"12_CR13","unstructured":"Downey, R.G., Fellows, M.R.: Fixed parameter tractability and completeness. In: Ambos-Spies, K., Homer, S., Sch\u00f6ning, U. (eds.) Complexity Theory: Current Research, Dagstuhl Workshop, February 2\u20138, 1992, pp. 191\u2013225. Cambridge University Press (1992)"},{"key":"12_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1007\/978-3-540-28639-4_22","volume-title":"Parameterized and Exact Computation","author":"SS Fedin","year":"2004","unstructured":"Fedin, S.S., Kulikov, A.S.: Automated proofs of upper bounds on the running time of splitting algorithms. In: Downey, R., Fellows, M., Dehne, F. (eds.) IWPEC 2004. LNCS, vol. 3162, pp. 248\u2013259. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-28639-4_22"},{"issue":"14","key":"12_CR15","doi-asserted-by":"publisher","first-page":"3157","DOI":"10.1080\/00207160903176868","volume":"87","author":"H Fernau","year":"2010","unstructured":"Fernau, H.: Parameterized algorithmics for $$d$$-Hitting Set. Int. J. Comput. Math. 87(14), 3157\u20133174 (2010). https:\/\/doi.org\/10.1080\/00207160903176868","journal-title":"Int. J. Comput. Math."},{"key":"12_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/978-3-642-02017-9_9","volume-title":"Theory and Applications of Models of Computation","author":"H Fernau","year":"2009","unstructured":"Fernau, H., Raible, D.: Searching trees: an essay. In: Chen, J., Cooper, S.B. (eds.) TAMC 2009. LNCS, vol. 5532, pp. 59\u201370. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-02017-9_9"},{"issue":"7\u20139","key":"12_CR17","doi-asserted-by":"publisher","first-page":"1045","DOI":"10.1016\/j.tcs.2009.11.012","volume":"411","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Gaspers, S., Kratsch, D., Liedloff, M., Saurabh, S.: Iterative compression and exact algorithms. Theor. Comput. Sci. 411(7\u20139), 1045\u20131053 (2010). https:\/\/doi.org\/10.1016\/j.tcs.2009.11.012","journal-title":"Theor. Comput. Sci."},{"key":"12_CR18","doi-asserted-by":"publisher","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: A measure & conquer approach for the analysis of exact algorithms. J. ACM 56(5), 25:1\u201325:32 (2009). https:\/\/doi.org\/10.1145\/1552285.1552286","DOI":"10.1145\/1552285.1552286"},{"key":"12_CR19","doi-asserted-by":"publisher","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-16533-7","DOI":"10.1007\/978-3-642-16533-7"},{"issue":"1","key":"12_CR20","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/s00778-015-0392-3","volume":"25","author":"S Funke","year":"2016","unstructured":"Funke, S., Nusser, A., Storandt, S.: On $$k$$-path covers and their applications. VLDB J. 25(1), 103\u2013123 (2016). https:\/\/doi.org\/10.1007\/s00778-015-0392-3","journal-title":"VLDB J."},{"key":"12_CR21","unstructured":"Gaspers, S.: Exponential Time Algorithms - Structures, Measures, and Bounds. VDM Verlag Dr. Mueller e.K. (2010). https:\/\/www.cse.unsw.edu.au\/sergeg\/SergeBookETA2010_print.pdf"},{"issue":"4","key":"12_CR22","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/s00453-004-1090-5","volume":"39","author":"J Gramm","year":"2004","unstructured":"Gramm, J., Guo, J., H\u00fcffner, F., Niedermeier, R.: Automated generation of search tree algorithms for hard graph modification problems. Algorithmica 39(4), 321\u2013347 (2004). https:\/\/doi.org\/10.1007\/s00453-004-1090-5","journal-title":"Algorithmica"},{"key":"12_CR23","unstructured":"Harris, D.G., Narayanaswamy, N.S.: A faster algorithm for vertex cover parameterized by solution size. CoRR abs\/2205.08022 (2022), https:\/\/arxiv.org\/abs\/2205.08022"},{"issue":"4","key":"12_CR24","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.: A faster FPT algorithm for 3-path vertex cover. Inf. Process. Lett. 116(4), 273\u2013278 (2016). https:\/\/doi.org\/10.1016\/j.ipl.2015.12.002","journal-title":"Inf. Process. Lett."},{"key":"12_CR25","doi-asserted-by":"crossref","unstructured":"Kojevnikov, A., Kulikov, A.S.: A new approach to proving upper bounds for MAX-2-SAT. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22\u201326, 2006, pp. 11\u201317. ACM Press (2006). http:\/\/dl.acm.org\/citation.cfm?id=1109557.1109559","DOI":"10.1145\/1109557.1109559"},{"key":"12_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1007\/11499107_35","volume-title":"Theory and Applications of Satisfiability Testing","author":"AS Kulikov","year":"2005","unstructured":"Kulikov, A.S.: Automated generation of simplification rules for SAT and MAXSAT. In: Bacchus, F., Walsh, T. (eds.) SAT 2005. LNCS, vol. 3569, pp. 430\u2013436. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11499107_35"},{"issue":"2","key":"12_CR27","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"JM Lewis","year":"1980","unstructured":"Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. J. Comput. Syst. Sci. 20(2), 219\u2013230 (1980). https:\/\/doi.org\/10.1016\/0022-0000(80)90060-4","journal-title":"J. Comput. Syst. Sci."},{"key":"12_CR28","doi-asserted-by":"publisher","unstructured":"Lokshtanov, Daniel, Saurabh, Saket, Such\u00fd, Ond\u0159ej: Solving multicut faster than 2n. In: Schulz, Andreas S.., Wagner, Dorothea (eds.) ESA 2014. LNCS, vol. 8737, pp. 666\u2013676. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-44777-2_55","DOI":"10.1007\/978-3-662-44777-2_55"},{"key":"12_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1007\/3-540-49116-3_53","volume-title":"STACS 99","author":"R Niedermeier","year":"1999","unstructured":"Niedermeier, R., Rossmanith, P.: Upper bounds for vertex cover further improved. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 561\u2013570. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/3-540-49116-3_53"},{"issue":"1","key":"12_CR30","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/S1570-8667(03)00009-1","volume":"1","author":"R Niedermeier","year":"2003","unstructured":"Niedermeier, R., Rossmanith, P.: An efficient fixed-parameter algorithm for 3-hitting set. J. Discrete Algorithms 1(1), 89\u2013102 (2003). https:\/\/doi.org\/10.1016\/S1570-8667(03)00009-1","journal-title":"J. Discrete Algorithms"},{"key":"12_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1007\/978-3-642-12368-9_8","volume-title":"Information Security Theory and Practices. Security and Privacy of Pervasive Systems and Smart Devices","author":"M Novotn\u00fd","year":"2010","unstructured":"Novotn\u00fd, M.: Design and analysis of a generalized canvas protocol. In: Samarati, P., Tunstall, M., Posegga, J., Markantonakis, K., Sauveron, D. (eds.) WISTP 2010. LNCS, vol. 6033, pp. 106\u2013121. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-12368-9_8"},{"issue":"17","key":"12_CR32","doi-asserted-by":"publisher","first-page":"2147","DOI":"10.1016\/j.dam.2011.07.001","volume":"159","author":"JMM van Rooij","year":"2011","unstructured":"van Rooij, J.M.M., Bodlaender, H.L.: Exact algorithms for dominating set. Discret. Appl. Math. 159(17), 2147\u20132164 (2011). https:\/\/doi.org\/10.1016\/j.dam.2011.07.001","journal-title":"Discret. Appl. Math."},{"issue":"4","key":"12_CR33","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1007\/s00453-011-9546-x","volume":"64","author":"JMM van Rooij","year":"2012","unstructured":"van Rooij, J.M.M., Bodlaender, H.L.: Exact algorithms for edge domination. Algorithmica 64(4), 535\u2013563 (2012). https:\/\/doi.org\/10.1007\/s00453-011-9546-x","journal-title":"Algorithmica"},{"key":"12_CR34","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.: Parameterized algorithm for 3-path vertex cover. Theor. Comput. Sci. 783, 1\u20138 (2019). https:\/\/doi.org\/10.1016\/j.tcs.2019.03.013","journal-title":"Theor. Comput. Sci."},{"key":"12_CR35","doi-asserted-by":"publisher","unstructured":"Tsur, D.: An $$O^*(2.619^k)$$ algorithm for 4-path vertex cover. Discret. Appl. Math. 291, 1\u201314 (2021). https:\/\/doi.org\/10.1016\/j.dam.2020.11.019","DOI":"10.1016\/j.dam.2020.11.019"},{"key":"12_CR36","doi-asserted-by":"publisher","unstructured":"Tsur, D.: Faster parameterized algorithms for two vertex deletion problems. Theor. Comput. Sci. 940(Part), 112\u2013123 (2023). https:\/\/doi.org\/10.1016\/j.tcs.2022.10.044","DOI":"10.1016\/j.tcs.2022.10.044"},{"issue":"2","key":"12_CR37","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.: A fixed-parameter algorithm for the vertex cover $${P}_3$$ problem. Inf. Process. Lett. 115(2), 96\u201399 (2015). https:\/\/doi.org\/10.1016\/j.ipl.2014.06.018","journal-title":"Inf. Process. Lett."},{"key":"12_CR38","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1016\/j.dam.2015.06.032","volume":"200","author":"J Tu","year":"2016","unstructured":"Tu, J., Jin, Z.: An FPT algorithm for the vertex cover $${P}_4$$ problem. Discret. Appl. Math. 200, 186\u2013190 (2016). https:\/\/doi.org\/10.1016\/j.dam.2015.06.032","journal-title":"Discret. Appl. Math."},{"key":"12_CR39","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.tcs.2016.04.043","volume":"657","author":"M Xiao","year":"2017","unstructured":"Xiao, M., Kou, S.: Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems. Theor. Comput. Sci. 657, 86\u201397 (2017). https:\/\/doi.org\/10.1016\/j.tcs.2016.04.043","journal-title":"Theor. Comput. Sci."},{"key":"12_CR40","doi-asserted-by":"publisher","unstructured":"Xiao, M., Kou, S.: Kernelization and parameterized algorithms for 3-path vertex cover. In: Proc. TAMC 2017, pp. 654\u2013668 (2017). https:\/\/doi.org\/10.1007\/978-3-319-55911-7_47","DOI":"10.1007\/978-3-319-55911-7_47"},{"key":"12_CR41","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/j.ic.2017.06.001","volume":"255","author":"M Xiao","year":"2017","unstructured":"Xiao, M., Nagamochi, H.: Exact algorithms for maximum independent set. Inf. Comput. 255, 126\u2013146 (2017). https:\/\/doi.org\/10.1016\/j.ic.2017.06.001","journal-title":"Inf. Comput."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-43380-1_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,22]],"date-time":"2023-09-22T20:30:38Z","timestamp":1695414638000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-43380-1_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031433795","9783031433801"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-43380-1_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"23 September 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Fribourg","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Switzerland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 June 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 June 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"49","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/events.unifr.ch\/wg2023\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}