{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T10:21:40Z","timestamp":1768731700406,"version":"3.49.0"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2017,11,14]],"date-time":"2017-11-14T00:00:00Z","timestamp":1510617600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"ERC","award":["Starting Grant 306465"],"award-info":[{"award-number":["Starting Grant 306465"]}]},{"name":"Conicyt","award":["PII20150140"],"award-info":[{"award-number":["PII20150140"]}]},{"name":"Millenium Nucleus","award":["Information and Coordination in Networks RC130003"],"award-info":[{"award-number":["Information and Coordination in Networks RC130003"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2018,9]]},"DOI":"10.1007\/s10107-017-1199-3","type":"journal-article","created":{"date-parts":[[2017,11,14]],"date-time":"2017-11-14T14:40:32Z","timestamp":1510670432000},"page":"433-461","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["New algorithms for maximum disjoint paths based on tree-likeness"],"prefix":"10.1007","volume":"171","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1129-3289","authenticated-orcid":false,"given":"Krzysztof","family":"Fleszar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4721-5354","authenticated-orcid":false,"given":"Matthias","family":"Mnich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2601-6452","authenticated-orcid":false,"given":"Joachim","family":"Spoerhase","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,11,14]]},"reference":[{"key":"1199_CR1","doi-asserted-by":"crossref","unstructured":"Adler, I., Kolliopoulos, S.G., Krause, P.K., Lokshtanov, D., Saurabh, S., Thilikos, D.: Tight bounds for linkages in planar graphs. In: Proceedings of ICALP 2011, Lecture Notes in Computer Science, vol. 6755, pp. 110\u2013121 (2011)","DOI":"10.1007\/978-3-642-22006-7_10"},{"key":"1199_CR2","doi-asserted-by":"crossref","unstructured":"Andrews, M.: Approximation algorithms for the edge-disjoint paths problem via R\u00e4cke decompositions. In: Proceedings of FOCS 2010, pp. 277\u2013286 (2010)","DOI":"10.1109\/FOCS.2010.33"},{"key":"1199_CR3","unstructured":"Aumann, Y., Rabani, Y.: Improved bounds for all optical routing. In: Proceedings of SODA 1995, pp. 567\u2013576 (1995)"},{"issue":"1","key":"1199_CR4","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1137\/S0097539794285983","volume":"27","author":"Y Aumann","year":"1998","unstructured":"Aumann, Y., Rabani, Y.: An $$\\cal{O}$$ O (log k) approximate min-cut max-flow theorem and approximation algorithm. SIAM J. Comput. 27(1), 291\u2013301 (1998)","journal-title":"SIAM J. Comput."},{"key":"1199_CR5","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Gawlick, R., Leighton, T., Rabani, Y.: On-line admission control and circuit routing for high performance computing and communication. In: Proceedings of FOCS 1994, pp. 412\u2013423 (1994)","DOI":"10.1109\/SFCS.1994.365675"},{"issue":"3","key":"1199_CR6","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1137\/S0895480196305124","volume":"12","author":"V Bafna","year":"1999","unstructured":"Bafna, V., Berman, P., Fujito, T.: A $$2$$ 2 -approximation algorithm for the undirected feedback vertex set problem. SIAM J. Discrete Math. 12(3), 289\u2013297 (1999). (electronic)","journal-title":"SIAM J. Discrete Math."},{"issue":"35","key":"1199_CR7","doi-asserted-by":"crossref","first-page":"4570","DOI":"10.1016\/j.tcs.2011.04.039","volume":"412","author":"HL Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Thomass\u00e9, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theoret. Comput. Sci. 412(35), 4570\u20134578 (2011)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"1199_CR8","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1137\/S0097539795290805","volume":"28","author":"AZ Broder","year":"1999","unstructured":"Broder, A.Z., Frieze, A.M., Suen, S., Upfal, E.: Optimal construction of edge-disjoint paths in random graphs. SIAM J. Comput. 28(2), 541\u2013573 (1999). (electronic)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"1199_CR9","doi-asserted-by":"crossref","first-page":"976","DOI":"10.1137\/S0097539792232021","volume":"23","author":"AZ Broder","year":"1994","unstructured":"Broder, A.Z., Frieze, A.M., Upfal, E.: Existence and construction of edge-disjoint paths on expander graphs. SIAM J. Comput. 23(5), 976\u2013989 (1994)","journal-title":"SIAM J. Comput."},{"key":"1199_CR10","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Ene, A.: Poly-logarithmic approximation for maximum node disjoint paths with constant congestion. In: Proceedings of SODA 2013, pp. 326\u2013341 (2013)","DOI":"10.1137\/1.9781611973105.24"},{"key":"1199_CR11","doi-asserted-by":"crossref","first-page":"137","DOI":"10.4086\/toc.2006.v002a007","volume":"2","author":"C Chekuri","year":"2006","unstructured":"Chekuri, C., Khanna, S., Shepherd, F.B.: An $$\\cal{O}(\\sqrt{n})$$ O ( n ) approximation and integrality gap for disjoint paths and unsplittable flow. Theory Comput. 2, 137\u2013146 (2006)","journal-title":"Theory Comput."},{"issue":"3","key":"1199_CR12","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1007\/s00453-007-9129-z","volume":"54","author":"C Chekuri","year":"2009","unstructured":"Chekuri, C., Khanna, S., Shepherd, F.B.: A note on multiflows and treewidth. Algorithmica 54(3), 400\u2013412 (2009)","journal-title":"Algorithmica"},{"key":"1199_CR13","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Mydlarz, M., Shepherd, F.B.: Multicommodity demand flow in a tree and packing integer programs. ACM Trans. Algorithms 3(3), Art. 27, 23 (2007)","DOI":"10.1145\/1273340.1273343"},{"key":"1199_CR14","unstructured":"Chekuri, C., Naves, G., Shepherd, F.B.: Maximum edge-disjoint paths in $$k$$ k -sums of graphs. Technical Report. http:\/\/arxiv.org\/abs\/1303.4897"},{"key":"1199_CR15","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Naves, G., Shepherd, F.B.: Maximum edge-disjoint paths in $$k$$ k -sums of graphs. In: Proceedings of ICALP 2013, Lecture Notes in Computer Sciences, vol. 7965, pp. 328\u2013339 (2013)","DOI":"10.1007\/978-3-642-39206-1_28"},{"issue":"2","key":"1199_CR16","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1016\/j.jctb.2012.11.002","volume":"103","author":"C Chekuri","year":"2013","unstructured":"Chekuri, C., Shepherd, F.B., Weibel, C.: Flow-cut gaps for integer and fractional multiflows. J. Comb. Theory Ser. B 103(2), 248\u2013273 (2013)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1199_CR17","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J.: Routing in undirected graphs with constant congestion. In: Proceedings of STOC 2012, pp. 855\u2013874 (2012)","DOI":"10.1145\/2213977.2214054"},{"key":"1199_CR18","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., Kim, D.H.K., Li, S.: Improved approximation for node-disjoint paths in planar graphs. In: Proceedings of STOC 2016, pp. 556\u2013569 (2016)","DOI":"10.1145\/2897518.2897538"},{"key":"1199_CR19","first-page":"86","volume":"2017","author":"J Chuzhoy","year":"2017","unstructured":"Chuzhoy, J., Kim, D.H.K., Nimavat, R.: New hardness results for routing on disjoint paths. Proc. STOC 2017, 86\u201399 (2017)","journal-title":"Proc. STOC"},{"key":"1199_CR20","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., Li, S.: A polylogarithmic approximation algorithm for edge-disjoint paths with congestion 2. In: Proceedings of FOCS 2012, pp. 233\u2013242 (2012)","DOI":"10.1109\/FOCS.2012.54"},{"key":"1199_CR21","unstructured":"Ene, A., Mnich, M., Pilipczuk, M., Risteski, A.: On routing disjoint paths in bounded treewidth graphs. In: Proceedings of SWAT 2016, Leibniz International Proceedings in Informatics, vol.\u00a053, pp. 15:1\u201315:15 (2016)"},{"key":"1199_CR22","doi-asserted-by":"crossref","unstructured":"Even, S., Itai, A., Shamir, A.: On the complexity of time table and multi-commodity flow problems. In: Proceedings of FOCS 1975, SFCS \u201975, pp. 184\u2013193. IEEE Computer Society, Washington, DC, USA (1975)","DOI":"10.1109\/SFCS.1975.21"},{"issue":"1","key":"1199_CR23","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"MR Fellows","year":"2009","unstructured":"Fellows, M.R., Hermelin, D., Rosamond, F., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theoret. Comput. Sci. 410(1), 53\u201361 (2009)","journal-title":"Theoret. Comput. Sci."},{"key":"1199_CR24","unstructured":"Fleszar, K., Mnich, M., Spoerhase, J.: New algorithms for maximum disjoint paths based on tree-likeness. In: Proceedings of ESA 2016, pp. 42:1\u201342:17 (2016)"},{"issue":"6","key":"1199_CR25","doi-asserted-by":"crossref","first-page":"1790","DOI":"10.1137\/S0097539700366103","volume":"30","author":"AM Frieze","year":"2001","unstructured":"Frieze, A.M.: Edge-disjoint paths in expander graphs. SIAM J. Comput. 30(6), 1790\u20131801 (2001). (electronic)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"1199_CR26","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF02523685","volume":"18","author":"N Garg","year":"1997","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18(1), 3\u201320 (1997)","journal-title":"Algorithmica"},{"issue":"1","key":"1199_CR27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/S089548010138917X","volume":"21","author":"O G\u00fcnl\u00fck","year":"2007","unstructured":"G\u00fcnl\u00fck, O.: A new min-cut max-flow ratio for multicommodity flows. SIAM J. Discrete Math. 21(1), 1\u201315 (2007)","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"1199_CR28","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I Holyer","year":"1981","unstructured":"Holyer, I.: The NP-completeness of edge-coloring. SIAM J. Comput. 10(4), 718\u2013720 (1981)","journal-title":"SIAM J. Comput."},{"key":"1199_CR29","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1002\/net.1975.5.1.45","volume":"5","author":"RM Karp","year":"1975","unstructured":"Karp, R.M.: On the computational complexity of combinatorial problems. Networks 5, 45\u201368 (1975)","journal-title":"Networks"},{"key":"1199_CR30","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K.-I., Wollan, P.: A shorter proof of the graph minor algorithm: the unique linkage theorem. In: Proceedings of STOC 2010, pp. 687\u2013694 (2010)","DOI":"10.1145\/1806689.1806784"},{"key":"1199_CR31","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K.-i., Kobayashi, Y.: An $$\\cal O\\it (\\log n)$$ O ( log n ) -Approximation Algorithm for the Disjoint Paths Problem in Eulerian Planar Graphs and 4-Edge-Connected Planar Graphs, pp. 274\u2013286 (2010)","DOI":"10.1007\/978-3-642-15369-3_21"},{"key":"1199_CR32","doi-asserted-by":"crossref","unstructured":"Kleinberg, J., Rubinfeld, R.: Short paths in expander graphs. In: Proceedings of FOCS 1996, pp. 86\u201395 (1996)","DOI":"10.1109\/SFCS.1996.548467"},{"key":"1199_CR33","doi-asserted-by":"crossref","unstructured":"Kleinberg, J., Tardos, \u00c9.: Disjoint paths in densely embedded graphs. In: Proceedings of FOCS 1995, pp. 52\u201361 (1995)","DOI":"10.1109\/SFCS.1995.492462"},{"issue":"1","key":"1199_CR34","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1006\/jcss.1998.1579","volume":"57","author":"J Kleinberg","year":"1998","unstructured":"Kleinberg, J., Tardos, \u00c9.: Approximations for the disjoint paths problem in high-diameter planar networks. J. Comput. Syst. Sci. 57(1), 61\u201373 (1998)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"1199_CR35","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/s10107-002-0370-6","volume":"99","author":"SG Kolliopoulos","year":"2004","unstructured":"Kolliopoulos, S.G., Stein, C.: Approximating disjoint-path problems using packing integer programs. Math. Program. 99(1), 63\u201387 (2004)","journal-title":"Math. Program."},{"issue":"6","key":"1199_CR36","doi-asserted-by":"crossref","first-page":"787","DOI":"10.1145\/331524.331526","volume":"46","author":"T Leighton","year":"1999","unstructured":"Leighton, T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM 46(6), 787\u2013832 (1999)","journal-title":"J. ACM"},{"issue":"2","key":"1199_CR37","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/BF01200757","volume":"15","author":"N Linial","year":"1995","unstructured":"Linial, N., London, E., Rabinovich, Y.: The geometry of graphs and some of its algorithmic applications. Combinatorica 15(2), 215\u2013245 (1995)","journal-title":"Combinatorica"},{"key":"1199_CR38","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Ramanujan, M.S., Saurabh, S.: Linear time parameterized algorithms for subset feedback vertex set. In: Proceedings of ICALP 2015, pp. 935\u2013946 (2015)","DOI":"10.1007\/978-3-662-47672-7_76"},{"issue":"1\u20133","key":"1199_CR39","doi-asserted-by":"crossref","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. Discrete Appl. Math. 115(1\u20133), 177\u2013186 (2001)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"1199_CR40","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P Raghavan","year":"1987","unstructured":"Raghavan, P., Tompson, C.D.: Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7(4), 365\u2013374 (1987)","journal-title":"Combinatorica"},{"issue":"5","key":"1199_CR41","doi-asserted-by":"crossref","first-page":"1856","DOI":"10.1137\/080715093","volume":"39","author":"S Rao","year":"2010","unstructured":"Rao, S., Zhou, S.: Edge disjoint paths in moderately connected graphs. SIAM J. Comput. 39(5), 1856\u20131887 (2010)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"1199_CR42","doi-asserted-by":"crossref","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. Comb. Theory Ser. B 63(1), 65\u2013110 (1995)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1199_CR43","unstructured":"Scheffler, P.: A practical linear time algorithm for disjoint paths in graphs with bounded tree-width. Technical Report TR 396\/1994, FU Berlin, Fachbereich 3 Mathematik (1994)"},{"key":"1199_CR44","doi-asserted-by":"crossref","unstructured":"S\u00e9guin-Charbonneau, L., Shepherd, F.B.: Maximum edge-disjoint paths in planar graphs with congestion 2. In: Proceedings of FOCS 2011, pp. 200\u2013209 (2011)","DOI":"10.1109\/FOCS.2011.30"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-017-1199-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-017-1199-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-017-1199-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,27]],"date-time":"2025-06-27T00:40:43Z","timestamp":1750984843000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-017-1199-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11,14]]},"references-count":44,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2018,9]]}},"alternative-id":["1199"],"URL":"https:\/\/doi.org\/10.1007\/s10107-017-1199-3","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,11,14]]}}}