{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T10:10:41Z","timestamp":1784110241289,"version":"3.55.0"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031834370","type":"print"},{"value":"9783031834387","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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":[[2025]]},"DOI":"10.1007\/978-3-031-83438-7_13","type":"book-chapter","created":{"date-parts":[[2025,2,4]],"date-time":"2025-02-04T21:56:36Z","timestamp":1738706196000},"page":"147-159","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Polynomial-Time Algorithms for\u00a0Path Cover on\u00a0Trees and\u00a0Graphs of\u00a0Bounded Treewidth"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8198-693X","authenticated-orcid":false,"given":"Florent","family":"Foucaud","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6694-777X","authenticated-orcid":false,"given":"Atrayee","family":"Majumder","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2509-6972","authenticated-orcid":false,"given":"Tobias","family":"M\u00f6mke","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-3607-9611","authenticated-orcid":false,"given":"Aida","family":"Roshany-Tabrizi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,2,5]]},"reference":[{"key":"13_CR1","unstructured":"Akiyama, T., Nishizeki, T., Saito, N.: NP-completeness of the Hamiltonian cycle problem for bipartite graphs. J. Inform. Process. 3(2), 73\u201376 (11980\/81)"},{"issue":"1\u20133","key":"13_CR2","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/0166-218X(94)00142-Z","volume":"62","author":"G Andreatta","year":"1995","unstructured":"Andreatta, G., Mason, F.: Path covering problems and testing of printed circuits. Discret. Appl. Math. 62(1\u20133), 5\u201313 (1995)","journal-title":"Discret. Appl. Math."},{"key":"13_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-319-03898-8_5","volume-title":"Parameterized and Exact Computation","author":"HL Bodlaender","year":"2013","unstructured":"Bodlaender, H.L., Bonsma, P., Lokshtanov, D.: The fine details of fast dynamic programming over tree decompositions. In: Gutin, G., Szeider, S. (eds.) IPEC 2013. LNCS, vol. 8246, pp. 41\u201353. Springer, Cham (2013). https:\/\/doi.org\/10.1007\/978-3-319-03898-8_5"},{"key":"13_CR4","doi-asserted-by":"crossref","unstructured":"Boesch, F., Chen, S., McHugh, J.: On covering the points of a graph with point disjoint paths. In: Graphs and Combinatorics, pp. 201\u2013212. Springer (1974)","DOI":"10.1007\/BFb0066442"},{"key":"13_CR5","doi-asserted-by":"crossref","unstructured":"C\u00e1ceres, M., Cairo, M., Mumey, B., Rizzi, R., Tomescu, A.I.: Sparsifying, shrinking and splicing for minimum path cover in parameterized linear time. In: Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, pp. 359\u2013376 (2022)","DOI":"10.1137\/1.9781611977073.18"},{"key":"13_CR6","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. The MIT Press, 3rd edition (2009)"},{"issue":"3","key":"13_CR7","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1137\/11083856X","volume":"42","author":"DG Corneil","year":"2013","unstructured":"Corneil, D.G., Dalton, B., Habib, M.: LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs. SIAM J. Comput. 42(3), 792\u2013807 (2013)","journal-title":"SIAM J. Comput."},{"key":"13_CR8","doi-asserted-by":"crossref","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015)","DOI":"10.1007\/978-3-319-21275-3"},{"key":"13_CR9","doi-asserted-by":"crossref","unstructured":"Cygan, M., et al.: Solving connectivity problems parameterized by treewidth in single exponential time. ACM Trans. Algorithms 18(2), 17:1\u201317:31 (2022)","DOI":"10.1145\/3506707"},{"issue":"6","key":"13_CR10","doi-asserted-by":"publisher","first-page":"3673","DOI":"10.1109\/TCBB.2021.3131203","volume":"19","author":"M C\u00e1ceres","year":"2022","unstructured":"C\u00e1ceres, M., et al.: Safety in multi-assembly via paths appearing in all path covers of a dag. IEEE\/ACM Trans. Comput. Biol. Bioinf. 19(6), 3673\u20133684 (2022)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf."},{"key":"13_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/978-3-031-30448-4_14","volume-title":"Algorithms and Complexity","author":"H Fernau","year":"2023","unstructured":"Fernau, H., Foucaud, F., Mann, K., Padariya, U., Rao, K.N.R.: Parameterizing path partitions. In: Mavronicolas, M. (ed.) CIAC 2023. LNCS, vol. 13898, pp. 187\u2013201. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-30448-4_14"},{"issue":"2","key":"13_CR12","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1017\/S1446181100013894","volume":"44","author":"DS Franzblau","year":"2002","unstructured":"Franzblau, D.S., Raychaudhuri, A.: Optimal hamiltonian completions and path covers for trees, and a reduction to maximum flow. ANZIAM J. 44(2), 193\u2013204 (2002)","journal-title":"ANZIAM J."},{"key":"13_CR13","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1007\/BFb0066448","volume-title":"Graphs and Combinatorics","author":"S Goodman","year":"1974","unstructured":"Goodman, S., Hedetniemi, S.: On the hamiltonian completion problem. In: Bari, R.A., Harary, F. (eds.) Graphs and Combinatorics, pp. 262\u2013272. Springer, Berlin Heidelberg (1974)"},{"key":"13_CR14","doi-asserted-by":"crossref","unstructured":"Harary, F., Schwenk, A.: Evolution of the path number of a graph: covering and packing in graphs, II. Graph Theory and Computing, pp. 39\u201345 (1972)","DOI":"10.1016\/B978-1-4832-3187-7.50009-X"},{"issue":"17","key":"13_CR15","doi-asserted-by":"publisher","first-page":"2242","DOI":"10.1016\/j.dam.2007.06.001","volume":"155","author":"R Hung","year":"2007","unstructured":"Hung, R., Chang, M.: Finding a minimum path cover of a distance-hereditary graph in polynomial time. Discret. Appl. Math. 155(17), 2242\u20132256 (2007)","journal-title":"Discret. Appl. Math."},{"key":"13_CR16","doi-asserted-by":"crossref","unstructured":"Kloks, T.: Treewidth: computations and approximations. Springer (1994)","DOI":"10.1007\/BFb0045375"},{"key":"13_CR17","doi-asserted-by":"crossref","unstructured":"Korhonen, T.: A single-exponential time 2-approximation algorithm for treewidth. In: 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, pp. 184\u2013192 (2021)","DOI":"10.1109\/FOCS52979.2021.00026"},{"issue":"2","key":"13_CR18","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/0020-0190(76)90080-6","volume":"5","author":"S Kundu","year":"1976","unstructured":"Kundu, S.: A linear algorithm for the hamiltonian completion number of a tree. Inf. Process. Lett. 5(2), 55\u201357 (1976)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"13_CR19","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/j.ipl.2005.09.006","volume":"97","author":"G Lin","year":"2006","unstructured":"Lin, G., Cai, Z., Lin, D.: Vertex covering by paths on trees with its applications in machine translation. Inf. Process. Lett. 97(2), 73\u201381 (2006)","journal-title":"Inf. Process. Lett."},{"issue":"8","key":"13_CR20","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/0898-1221(95)00139-P","volume":"30","author":"R Lin","year":"1995","unstructured":"Lin, R., Olariu, S., Pruesse, G.: An optimal path cover algorithm for cographs. Comput. Math. Appl. 30(8), 75\u201383 (1995)","journal-title":"Comput. Math. Appl."},{"key":"13_CR21","unstructured":"Manuel, P.: Revisiting path-type covering and partitioning problems. arXiv preprint arXiv:1807.10613 (2018)"},{"key":"13_CR22","doi-asserted-by":"crossref","unstructured":"Ntafos, S., Hakimi, S.: On path cover problems in digraphs and applications to program testing. IEEE Trans. Softw. Eng. SE-5(5), 520\u2013529 (1979)","DOI":"10.1109\/TSE.1979.234213"},{"key":"13_CR23","doi-asserted-by":"crossref","unstructured":"Pan, J., Chang, G.J.: Path partition for graphs with special blocks. Discret. Appl. Math. 145(3), 429\u2013436 (2005)","DOI":"10.1016\/j.dam.2004.03.006"},{"key":"13_CR24","doi-asserted-by":"crossref","unstructured":"Rizzi, R., Tomescu, A.I., M\u00e4kinen, V.: On the complexity of minimum path cover with subpath constraints for multi-assembly. BMC Bioinform. 15(S-9), S5 (2014)","DOI":"10.1186\/1471-2105-15-S9-S5"},{"key":"13_CR25","doi-asserted-by":"crossref","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XIII. The disjoint paths problem. J. Combinatorial Theor. Ser. B 63(1), 65\u2013110 (1995)","DOI":"10.1006\/jctb.1995.1006"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-83438-7_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,4]],"date-time":"2025-02-04T21:56:40Z","timestamp":1738706200000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-83438-7_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031834370","9783031834387"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-83438-7_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"5 February 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CALDAM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Conference on Algorithms and Discrete Applied Mathematics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Coimbatore","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"India","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 February 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 February 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"caldam2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/caldam-2025-website.vercel.app\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}