{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T02:04:59Z","timestamp":1743041099952,"version":"3.40.3"},"publisher-location":"Singapore","reference-count":22,"publisher":"Springer Nature Singapore","isbn-type":[{"type":"print","value":"9789819628445"},{"type":"electronic","value":"9789819628452"}],"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-981-96-2845-2_18","type":"book-chapter","created":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T15:59:54Z","timestamp":1740067194000},"page":"281-295","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Min-Sum Disjoint Paths on\u00a0Subclasses of\u00a0Chordal Graphs"],"prefix":"10.1007","author":[{"given":"Bar","family":"Menashe","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,2,21]]},"reference":[{"key":"18_CR1","first-page":"100","volume":"49","author":"A Frank","year":"1990","unstructured":"Frank, A.: Packing paths, circuits, and cuts-a survey. Paths Flows VLSI-Layout 49, 100 (1990)","journal-title":"Paths Flows VLSI-Layout"},{"issue":"1\u20133","key":"18_CR2","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0166-218X(01)00223-2","volume":"115","author":"T Nishizeki","year":"2001","unstructured":"Nishizeki, T., Vygen, J., Zhou, X.: The edge-disjoint paths problem is NP-complete for series-parallel graphs. Discret. Appl. Math. 115(1\u20133), 177\u2013186 (2001)","journal-title":"Discret. Appl. Math."},{"key":"18_CR3","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, vol. 24. Springer (2003)"},{"key":"18_CR4","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/s11276-005-1765-0","volume":"11","author":"A Srinivas","year":"2005","unstructured":"Srinivas, A., Modiano, E.: Finding minimum energy disjoint paths in wireless ad-hoc networks. Wireless Netw. 11, 401\u2013417 (2005)","journal-title":"Wireless Netw."},{"issue":"1","key":"18_CR5","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.D.: Graph minors XIII. The disjoint paths problem. J. Combin. Theory Ser. B 63(1), 65\u2013110 (1995)","journal-title":"J. Combin. Theory Ser. B"},{"key":"18_CR6","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Saurabh, S., Zehavi, M.: Efficient graph minors theory and parameterized algorithms for (planar) disjoint paths. In: Treewidth, Kernels, and Algorithms - Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday, pp. 112\u2013128 (2020)","DOI":"10.1007\/978-3-030-42071-0_9"},{"issue":"2","key":"18_CR7","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/j.jctb.2011.07.004","volume":"102","author":"K Kawarabayashi","year":"2012","unstructured":"Kawarabayashi, K., Kobayashi, Y., Reed, B.: The disjoint paths problem in quadratic time. J. Combin. Theory Ser. B 102(2), 424\u2013435 (2012)","journal-title":"J. Combin. Theory Ser. B"},{"key":"18_CR8","doi-asserted-by":"crossref","unstructured":"Korhonen, T., Pilipczuk, M., Stamoulis, G.: Minor containment and disjoint paths in almost-linear time. In: Accepted to Proceedings of the 65th IEEE Symposium on Foundations of Computer Science (FOCS), FOCS 2024 (2024)","DOI":"10.1109\/FOCS61266.2024.00014"},{"key":"18_CR9","doi-asserted-by":"crossref","unstructured":"Cho, K., Oh, E., Oh, S.: Parameterized algorithm for the disjoint path problem on planar graphs: exponential in k$$ ^{\\text{2}}$$ and linear in n. In: Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, 22\u201325 January 2023, pp. 3734\u20133758 (2023)","DOI":"10.1137\/1.9781611977554.ch144"},{"key":"18_CR10","doi-asserted-by":"crossref","unstructured":"Wlodarczyk, M., Zehavi, M.: Planar disjoint paths, treewidth, and kernels. In: 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, 6\u20139 November 2023, pp. 649\u2013662 (2023)","DOI":"10.1109\/FOCS57990.2023.00044"},{"key":"18_CR11","doi-asserted-by":"crossref","unstructured":"Kammer, F., Tholey, T.: The k-disjoint paths problem on chordal graphs. In: Graph-Theoretic Concepts in Computer Science, 35th International Workshop, WG 2009, Montpellier, France, 24\u201326 June 2009, Revised Papers, pp. 190\u2013201 (2009)","DOI":"10.1007\/978-3-642-11409-0_17"},{"issue":"1","key":"18_CR12","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1007\/s00224-014-9580-6","volume":"57","author":"P Heggernes","year":"2015","unstructured":"Heggernes, P., Hof, P.V., Leeuwen, E.J.V., Saei, R.: Finding disjoint paths in split graphs. Theory Comput. Syst. 57(1), 140\u2013159 (2015)","journal-title":"Theory Comput. Syst."},{"key":"18_CR13","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.tcs.2017.09.023","volume":"734","author":"Y Yang","year":"2018","unstructured":"Yang, Y., Shrestha, Y.R., Li, W., Guo, J.: On the kernelization of split graph problems. Theoret. Comput. Sci. 734, 72\u201382 (2018)","journal-title":"Theoret. Comput. Sci."},{"issue":"10","key":"18_CR14","doi-asserted-by":"publisher","first-page":"112985","DOI":"10.1016\/j.disc.2022.112985","volume":"345","author":"J Ahn","year":"2022","unstructured":"Ahn, J., Jaffke, L., Kwon, O., Lima, P.T.: Well-partitioned chordal graphs. Discret. Math. 345(10), 112985 (2022)","journal-title":"Discret. Math."},{"key":"18_CR15","unstructured":"Chaudhary, J., Gahlawat, H., Wodarczyk, M., Zehavi, M.: Kernels for the disjoint paths problem on subclasses of chordal graphs (2023)"},{"key":"18_CR16","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 2021, Virtual Conference, 10\u201313 January 2021, pp. 169\u2013178 (2021)","DOI":"10.1137\/1.9781611976465.12"},{"issue":"3","key":"18_CR17","doi-asserted-by":"publisher","first-page":"1674","DOI":"10.1137\/22M1527398","volume":"37","author":"M Bentert","year":"2023","unstructured":"Bentert, M., Nichterlein, A., Renken, M., Zschoche, P.: Using a geometric lens to find-disjoint shortest paths. SIAM J. Discret. Math. 37(3), 1674\u20131703 (2023)","journal-title":"SIAM J. Discret. Math."},{"key":"18_CR18","doi-asserted-by":"crossref","unstructured":"Mari, M., Mukherjee, A., Pilipczuk, M., Sankowski, P.: Shortest disjoint paths on a grid. In: Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, 7\u201310 January 2024, pp. 346\u2013365 (2024)","DOI":"10.1137\/1.9781611977912.14"},{"issue":"6","key":"18_CR19","doi-asserted-by":"publisher","first-page":"1698","DOI":"10.1137\/18M1223034","volume":"48","author":"A Bjorklund","year":"2019","unstructured":"Bjorklund, A., Husfeldt, T.: Shortest two disjoint paths in polynomial time. SIAM J. Comput. 48(6), 1698\u20131710 (2019)","journal-title":"SIAM J. Comput."},{"key":"18_CR20","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/BF02579333","volume":"1","author":"PL Hammer","year":"1981","unstructured":"Hammer, P.L., Simeone, B.: The splittance of a graph. Combinatorica 1, 275\u2013284 (1981)","journal-title":"Combinatorica"},{"issue":"10","key":"18_CR21","doi-asserted-by":"publisher","first-page":"112985","DOI":"10.1016\/j.disc.2022.112985","volume":"345","author":"J Ahn","year":"2022","unstructured":"Ahn, J., Jaffke, L., Kwon, O.J., Lima, P.T.: Well-partitioned chordal graphs. Discret. Math. 345(10), 112985 (2022)","journal-title":"Discret. Math."},{"key":"18_CR22","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"JE Hopcroft","year":"1971","unstructured":"Hopcroft, J.E., Karp, R.M.: A $$n^{5\/2}$$ algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2, 225\u2013231 (1971)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-96-2845-2_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T16:00:00Z","timestamp":1740067200000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-96-2845-2_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9789819628445","9789819628452"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-981-96-2845-2_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"21 February 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WALCOM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference and Workshops on Algorithms and Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Chengdu","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","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":"27 February 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 March 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"walcom2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/tcsuestc.com\/walcom2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}