{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:08Z","timestamp":1740109268077,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,5,20]],"date-time":"2020-05-20T00:00:00Z","timestamp":1589932800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,5,20]],"date-time":"2020-05-20T00:00:00Z","timestamp":1589932800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2021,7]]},"DOI":"10.1007\/s10107-020-01513-1","type":"journal-article","created":{"date-parts":[[2020,5,20]],"date-time":"2020-05-20T11:02:35Z","timestamp":1589972555000},"page":"295-317","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Maximum edge-disjoint paths in planar graphs with congestion 2"],"prefix":"10.1007","volume":"188","author":[{"given":"Lo\u00efc","family":"S\u00e9guin-Charbonneau","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1972-1396","authenticated-orcid":false,"given":"F. Bruce","family":"Shepherd","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,5,20]]},"reference":[{"key":"1513_CR1","doi-asserted-by":"crossref","unstructured":"Andrews, M.: Approximation algorithms for the edge-disjoint paths problem via R\u00e4cke decompositions. In: 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pp. 277\u2013286 (2010)","DOI":"10.1109\/FOCS.2010.33"},{"issue":"5","key":"1513_CR2","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/s00493-010-2455-9","volume":"30","author":"M Andrews","year":"2010","unstructured":"Andrews, M., Chuzhoy, J., Guruswami, V., Khanna, S., Talwar, K., Zhang, L.: Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs. Combinatorica 30(5), 485\u2013520 (2010)","journal-title":"Combinatorica"},{"key":"1513_CR3","unstructured":"Chekuri, C., Khanna, S., Shepherd, F.B.: Edge-disjoint paths in planar graphs. In: 45th Annual IEEE Symposium on Foundations of Computer Science, 2004. Proceedings, pp. 71\u201380 (2004)"},{"key":"1513_CR4","unstructured":"Chekuri, C., Chuzhoy, J.: Maximum node-disjoint paths with congestion 2. Personal communication (2016)"},{"key":"1513_CR5","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Khanna, S., Bruce Shepherd, F.: Edge-disjoint paths in planar graphs with constant congestion. In: STOC \u201906: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, pp. 757\u2013766. ACM, New York, NY (2006)","DOI":"10.1145\/1132516.1132621"},{"key":"1513_CR6","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Naves, G., Bruce Shepherd, F.: Maximum edge-disjoint paths in k-sums of graphs. In: International Colloquium on Automata, Languages, and Programming, pp. 328\u2013339. Springer (2013)","DOI":"10.1007\/978-3-642-39206-1_28"},{"issue":"4","key":"1513_CR7","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1145\/1255443.1255444","volume":"54","author":"J Chen","year":"2007","unstructured":"Chen, J., Kleinberg, R.D., Lov\u00e1sz, L., Rajaraman, R., Sundaram, R., Vetta, A.: (Almost) tight bounds and existence theorems for single-commodity confluent flows. J. ACM 54(4), 16 (2007)","journal-title":"J. ACM"},{"key":"1513_CR8","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J.: Routing in undirected graphs with constant congestion. In: Proceedings of the 44th Symposium on Theory of Computing, pp. 855\u2013874. ACM (2012)","DOI":"10.1145\/2213977.2214054"},{"key":"1513_CR9","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., Li, S.: A polylogarithimic approximation algorithm for edge-disjoint paths with congestion 2. arXiv preprint arXiv:1208.1272 (2012)","DOI":"10.1109\/FOCS.2012.54"},{"key":"1513_CR10","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., Kim, D.H.K., Nimavat, R.: New hardness results for routing on disjoint paths. arXiv preprint arXiv:1611.05429 (2016)","DOI":"10.1145\/3055399.3055411"},{"key":"1513_CR11","doi-asserted-by":"publisher","DOI":"10.1002\/9781118033142","volume-title":"Combinatorial Optimization","author":"WJ Cook","year":"1997","unstructured":"Cook, W.J., Cunningham, W.H., Pulleyblank, W.R., Schrijver, A.: Combinatorial Optimization. Wiley-Interscience, Hoboken (1997)"},{"issue":"1","key":"1513_CR12","doi-asserted-by":"publisher","first-page":"17, 01","DOI":"10.1007\/s004930050043","volume":"19","author":"Y Dinitz","year":"1999","unstructured":"Dinitz, Y., Garg, N., Goemans, M.X.: On the single-source unsplittable flow problem. Combinatorica 19(1), 17, 01\u201341 (1999)","journal-title":"Combinatorica"},{"key":"1513_CR13","doi-asserted-by":"crossref","unstructured":"Donovan, P., Shepherd, B., Vetta, A., Wilfong, G.: Degree-constrained network flows. In: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of computing, pp. 681\u2013688. ACM (2007)","DOI":"10.1145\/1250790.1250889"},{"key":"1513_CR14","first-page":"49","volume-title":"Paths, Flows and VLSI-Layout","author":"A Frank","year":"1990","unstructured":"Frank, A.: Packing paths, cuts, and circuits\u2014a survey. In: Korte, B., Lov\u00e1sz, L., Pr\u00f6mel, H.J., Schrijver, A. (eds.) Paths, Flows and VLSI-Layout, pp. 49\u2013100. Springer, Berlin (1990)"},{"key":"1513_CR15","volume-title":"Connections in Combinatorial Optimization","author":"A Frank","year":"2011","unstructured":"Frank, A.: Connections in Combinatorial Optimization. Oxford University Press, Oxford (2011)"},{"issue":"1","key":"1513_CR16","doi-asserted-by":"publisher","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":"3","key":"1513_CR17","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1016\/S0022-0000(03)00066-7","volume":"67","author":"V Guruswami","year":"2003","unstructured":"Guruswami, V., Khanna, S., Rajaraman, R., Shepherd, B., Yannakakis, M.: Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. J. Comput. Syst. Sci. 67(3), 473\u2013496 (2003)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"1513_CR18","doi-asserted-by":"publisher","first-page":"1483","DOI":"10.1137\/130932326","volume":"47","author":"K Kawarabayashi","year":"2018","unstructured":"Kawarabayashi, K., Kobayashi, Y.: All-or-nothing multicommodity flow problem with bounded fractionality in planar graphs. SIAM J. Comput. 47(4), 1483\u20131504 (2018)","journal-title":"SIAM J. Comput."},{"key":"1513_CR19","doi-asserted-by":"crossref","unstructured":"Kleinberg, J., Tardos, \u00c9.: Approximations for the disjoint paths problem in high-diameter planar networks. In: Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, pp. 26\u201335. ACM (1995)","DOI":"10.1145\/225058.225075"},{"key":"1513_CR20","unstructured":"Kleinberg, J.M.: An approximation algorithm for the disjoint paths problem in even-degree planar graphs. In: FOCS \u201905: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 627\u2013636 (2005)"},{"issue":"1","key":"1513_CR21","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/S0095-8956(81)80012-3","volume":"31","author":"H Okamura","year":"1981","unstructured":"Okamura, H., Seymour, P.D.: Multicommodity flows in planar graphs. J. Combin. Theory Ser. B 31(1), 75\u201381 (1981)","journal-title":"J. Combin. Theory Ser. B"},{"key":"1513_CR22","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P Raghavan","year":"1987","unstructured":"Raghavan, P., Thompson, C.D.: Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7, 365\u2013374 (1987)","journal-title":"Combinatorica"},{"key":"1513_CR23","doi-asserted-by":"crossref","unstructured":"Seguin-Charbonneau, L., Shepherd, F.B.: Maximum edge-disjoint paths in planar graphs with congestion 2. In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 200\u2013209. IEEE (2011)","DOI":"10.1109\/FOCS.2011.30"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01513-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-020-01513-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01513-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,22]],"date-time":"2021-06-22T15:57:19Z","timestamp":1624377439000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-020-01513-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,20]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["1513"],"URL":"https:\/\/doi.org\/10.1007\/s10107-020-01513-1","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2020,5,20]]},"assertion":[{"value":"30 November 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 April 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 May 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}