{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T11:49:42Z","timestamp":1751456982946,"version":"3.40.3"},"publisher-location":"Cham","reference-count":33,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031304477"},{"type":"electronic","value":"9783031304484"}],"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-30448-4_14","type":"book-chapter","created":{"date-parts":[[2023,4,24]],"date-time":"2023-04-24T20:29:36Z","timestamp":1682368176000},"page":"187-201","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Parameterizing Path Partitions"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4444-3220","authenticated-orcid":false,"given":"Henning","family":"Fernau","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8198-693X","authenticated-orcid":false,"given":"Florent","family":"Foucaud","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0880-2513","authenticated-orcid":false,"given":"Kevin","family":"Mann","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4033-8044","authenticated-orcid":false,"given":"Utkarsh","family":"Padariya","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3422-6940","authenticated-orcid":false,"given":"K. N. Rajath","family":"Rao","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,4,25]]},"reference":[{"issue":"2","key":"14_CR1","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1145\/322003.322005","volume":"24","author":"FT Boesch","year":"1977","unstructured":"Boesch, F.T., Gimpel, J.F.: Covering points of a digraph with point-disjoint paths and its application to code optimization. J. ACM 24(2), 192\u2013198 (1977)","journal-title":"J. ACM"},{"key":"14_CR2","unstructured":"Chakraborty, D., Dailly, A., Das, S., Foucaud, F., Gahlawat, H., Ghosh, S.K.: Complexity and algorithms for isometric path cover on chordal graphs and beyond. In: Proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC 2022). LIPIcs, vol. 248, pp. 12:1\u201312:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022)"},{"key":"14_CR3","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press, Cambridge (2009)","edition":"3"},{"issue":"3","key":"14_CR4","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":"14_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"issue":"4","key":"14_CR6","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/BF00571188","volume":"8","author":"P Damaschke","year":"1992","unstructured":"Damaschke, P., Deogun, J.S., Kratsch, D., Steiner, G.: Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm. Order 8(4), 383\u2013391 (1992). https:\/\/doi.org\/10.1007\/BF00571188","journal-title":"Order"},{"key":"14_CR7","doi-asserted-by":"publisher","unstructured":"Dilworth, R.P.: A decomposition theorem for partially ordered sets. In: Gessel, I., Rota, G.C. (eds.) Classic Papers in Combinatorics, pp. 139\u2013144. Springer. Boston (2009). https:\/\/doi.org\/10.1007\/978-0-8176-4842-8_10","DOI":"10.1007\/978-0-8176-4842-8_10"},{"key":"14_CR8","unstructured":"Dumas, M., Foucaud, F., Perez, A., Todinca, I.: On graphs coverable by $$k$$ shortest paths. In: Proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC 2022). LIPIcs, vol. 248, pp. 40:1\u201340:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022)"},{"issue":"2","key":"14_CR9","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1016\/0196-6774(86)90002-7","volume":"7","author":"ME Dyer","year":"1986","unstructured":"Dyer, M.E., Frieze, A.M.: Planar 3DM is NP-complete. J. Algorithms 7(2), 174\u2013184 (1986)","journal-title":"J. Algorithms"},{"key":"14_CR10","doi-asserted-by":"crossref","unstructured":"Fernau, H., Foucaud, F., Mann, K., Padariya, U., Rao, K.N.R.: Parameterizing path partitions. arXiv preprint arXiv:2212.11653 (2022)","DOI":"10.1007\/978-3-031-30448-4_14"},{"key":"14_CR11","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S Fortune","year":"1980","unstructured":"Fortune, S., Hopcroft, J.E., Wyllie, J.: The directed subgraph homeomorphism problem. Theoret. Comput. Sci. 10, 111\u2013121 (1980)","journal-title":"Theoret. Comput. Sci."},{"key":"14_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, 193\u2013204 (2002)","journal-title":"ANZIAM J."},{"issue":"4","key":"14_CR13","first-page":"701","volume":"7","author":"DR Fulkerson","year":"1956","unstructured":"Fulkerson, D.R.: Note on Dilworth\u2019s decomposition theorem for partially ordered sets. Proc. Am. Math. Soc. 7(4), 701\u2013702 (1956)","journal-title":"Proc. Am. Math. Soc."},{"key":"14_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/978-3-319-03898-8_15","volume-title":"Parameterized and Exact Computation","author":"J Gajarsk\u00fd","year":"2013","unstructured":"Gajarsk\u00fd, J., Lampis, M., Ordyniak, S.: Parameterized algorithms for modular-width. In: Gutin, G., Szeider, S. (eds.) IPEC 2013. LNCS, vol. 8246, pp. 163\u2013176. Springer, Cham (2013). https:\/\/doi.org\/10.1007\/978-3-319-03898-8_15"},{"key":"14_CR15","volume-title":"Computers and Intractability","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. Freeman, NY (1979)"},{"key":"14_CR16","doi-asserted-by":"publisher","unstructured":"Goodman, S., Hedetniemi, S.: On the Hamiltonian completion problem. In: Bari, R.A., Harary, F. (eds.) Graphs and Combinatorics, pp. 262\u2013272. Springer, Heidelberg (1974). https:\/\/doi.org\/10.1007\/BFb0066448","DOI":"10.1007\/BFb0066448"},{"issue":"2","key":"14_CR17","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/j.jctb.2011.07.004","volume":"102","author":"KI Kawarabayashi","year":"2012","unstructured":"Kawarabayashi, K.I., Kobayashi, Y., Reed, B.: The disjoint paths problem in quadratic time. J. Comb. Theory Ser. B 102(2), 424\u2013435 (2012)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"14_CR18","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1145\/990518.990521","volume":"7","author":"MS Krishnamoorthy","year":"1975","unstructured":"Krishnamoorthy, M.S.: An NP-hard problem in bipartite graphs. ACM SIGACT News 7(1), 26 (1975)","journal-title":"ACM SIGACT News"},{"issue":"1","key":"14_CR19","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/s00453-011-9554-x","volume":"64","author":"M Lampis","year":"2012","unstructured":"Lampis, M.: Algorithmic meta-theorems for restrictions of treewidth. Algorithmica 64(1), 19\u201337 (2012)","journal-title":"Algorithmica"},{"issue":"1","key":"14_CR20","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/S0166-218X(02)00425-0","volume":"131","author":"HO Le","year":"2003","unstructured":"Le, H.O., Le, V.B., M\u00fcller, H.: Splitting a graph into disjoint induced paths or cycles. Discret. Appl. Math. 131(1), 199\u2013212 (2003)","journal-title":"Discret. Appl. Math."},{"key":"14_CR21","doi-asserted-by":"crossref","unstructured":"Lochet, W.: A polynomial time algorithm for the $$k$$-disjoint shortest paths problem. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 169\u2013178. SIAM (2021)","DOI":"10.1137\/1.9781611976465.12"},{"key":"14_CR22","unstructured":"Manuel, P.D.: Revisiting path-type covering and partitioning problems. arXiv preprint arXiv:1807.10613 (2018)"},{"issue":"4","key":"14_CR23","doi-asserted-by":"publisher","first-page":"1077","DOI":"10.7151\/dmgt.2236","volume":"41","author":"PD Manuel","year":"2021","unstructured":"Manuel, P.D.: On the isometric path partition problem. Discuss. Math. Graph Theory 41(4), 1077\u20131089 (2021)","journal-title":"Discuss. Math. Graph Theory"},{"issue":"5","key":"14_CR24","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1016\/j.orl.2006.12.004","volume":"35","author":"J Monnot","year":"2007","unstructured":"Monnot, J., Toulouse, S.: The path partition problem and related problems in bipartite graphs. Oper. Res. Lett. 35(5), 677\u2013684 (2007)","journal-title":"Oper. Res. Lett."},{"key":"14_CR25","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"},{"issue":"1","key":"14_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01408172","volume":"16","author":"SS Pinter","year":"1987","unstructured":"Pinter, S.S., Wolfstahl, Y.: On mapping processes to processors in distributed systems. Int. J. Parallel Prog. 16(1), 1\u201315 (1987)","journal-title":"Int. J. Parallel Prog."},{"issue":"1","key":"14_CR27","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.: Graph minors .XIII. The disjoint paths problem. J. Comb. Theory Ser. B 63(1), 65\u2013110 (1995)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"4","key":"14_CR28","doi-asserted-by":"publisher","first-page":"780","DOI":"10.1137\/S0097539792224061","volume":"23","author":"A Schrijver","year":"1994","unstructured":"Schrijver, A.: Finding $$k$$ disjoint paths in a directed planar graph. SIAM J. Comput. 23(4), 780\u2013788 (1994)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"14_CR29","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/070697781","volume":"24","author":"A Slivkins","year":"2010","unstructured":"Slivkins, A.: Parameterized tractability of edge-disjoint paths on directed acyclic graphs. SIAM J. Discrete Math. 24(1), 146\u2013157 (2010)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"14_CR30","doi-asserted-by":"publisher","first-page":"2147","DOI":"10.1016\/S0304-3975(02)00577-7","volume":"290","author":"G Steiner","year":"2003","unstructured":"Steiner, G.: On the $$k$$-path partition of graphs. Theoret. Comput. Sci. 290(3), 2147\u20132155 (2003)","journal-title":"Theoret. Comput. Sci."},{"key":"14_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1007\/978-3-540-70575-8_52","volume-title":"Automata, Languages and Programming","author":"M Tedder","year":"2008","unstructured":"Tedder, M., Corneil, D., Habib, M., Paul, C.: Simpler linear-time modular decomposition via recursive factorizing permutations. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5125, pp. 634\u2013645. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-70575-8_52"},{"key":"14_CR32","unstructured":"Thiessen, M., Gaertner, T.: Active learning of convex halfspaces on graphs. In: Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., Vaughan, J.W. (eds.) Proceedings of the 35th Conference on Neural Information Processing Systems (NeurIPS 2021), vol. 34, pp. 23413\u201323425. Curran Associates, Inc. (2021)"},{"key":"14_CR33","doi-asserted-by":"crossref","unstructured":"Wang, C., et al.: Optimizing cross-line dispatching for minimum electric bus fleet. IEEE Trans. Mob. Comput. 22(4) (2023)","DOI":"10.1109\/TMC.2021.3119421"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-30448-4_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,15]],"date-time":"2023-05-15T23:03:56Z","timestamp":1684191836000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-30448-4_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031304477","9783031304484"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-30448-4_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"25 April 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Larnaca","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Cyprus","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":"13 June 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 June 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ciac2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Open","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easy Chair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"49","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"25","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"51% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"6","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3 invited papers","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}