{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:43:53Z","timestamp":1767339833903},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642392054"},{"type":"electronic","value":"9783642392061"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39206-1_28","type":"book-chapter","created":{"date-parts":[[2013,7,2]],"date-time":"2013-07-02T17:20:16Z","timestamp":1372785616000},"page":"328-339","source":"Crossref","is-referenced-by-count":7,"title":["Maximum Edge-Disjoint Paths in k-Sums of Graphs"],"prefix":"10.1007","author":[{"given":"Chandra","family":"Chekuri","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guyslain","family":"Naves","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"F. Bruce","family":"Shepherd","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"5","key":"28_CR1","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\u00a030(5), 485\u2013520 (2010)","journal-title":"Combinatorica"},{"key":"28_CR2","unstructured":"Chekuri, C., Khanna, S., Shepherd, F.B.: Edge-disjoint paths in planar graphs. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 71\u201380 (2004)"},{"key":"28_CR3","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Khanna, S., Shepherd, F.B.: Multicommodity flow, well-linked terminals, and routing problems. In: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, pp. 183\u2013192. ACM (2005)","DOI":"10.1145\/1060590.1060618"},{"issue":"7","key":"28_CR4","doi-asserted-by":"publisher","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 \n                    \n                      \n                    \n                    $O(\\sqrt{n})$\n                   approximation and integrality gap for disjoint paths and unsplittable flow. Theory of Computing\u00a02(7), 137\u2013146 (2006)","journal-title":"Theory of Computing"},{"key":"28_CR5","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1137\/060674442","volume":"39","author":"C. Chekuri","year":"2009","unstructured":"Chekuri, C., Khanna, S., Shepherd, F.B.: Edge-disjoint paths in planar graphs with constant congestion. SIAM Journal on Computing\u00a039, 281\u2013301 (2009)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"28_CR6","doi-asserted-by":"publisher","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\u00a054(3), 400\u2013412 (2009)","journal-title":"Algorithmica"},{"issue":"2","key":"28_CR7","doi-asserted-by":"publisher","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. Journal of Combinatorial Theory, Series B\u00a0103(2), 248\u2013273 (2013)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"28_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":"28_CR9","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., Li, S.: A polylogarithimic approximation algorithm for edge-disjoint paths with congestion 2. In: Proc. of IEEE FOCS (2012)","DOI":"10.1109\/FOCS.2012.54"},{"issue":"2","key":"28_CR10","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., Wyllie, J.: The directed subgraph homeomorphism problem. Theoretical Computer Science\u00a010(2), 111\u2013121 (1980)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"28_CR11","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\u00a018(1), 3\u201320 (1997)","journal-title":"Algorithmica"},{"issue":"2","key":"28_CR12","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/s00493-004-0015-x","volume":"24","author":"A. Gupta","year":"2004","unstructured":"Gupta, A., Newman, I., Rabinovich, Y., Sinclair, A.: Cuts, trees and \u21131-embeddings of graphs. Combinatorica\u00a024(2), 233\u2013269 (2004)","journal-title":"Combinatorica"},{"key":"28_CR13","doi-asserted-by":"publisher","first-page":"682","DOI":"10.1145\/167088.167261","volume-title":"Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, STOC 1993","author":"P. Klein","year":"1993","unstructured":"Klein, P., Plotkin, S.A., Rao, S.: Excluded minors, network decomposition, and multicommodity flow. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, STOC 1993, pp. 682\u2013690. ACM, New York (1993)"},{"issue":"1","key":"28_CR14","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1006\/jcss.1998.1579","volume":"57","author":"J. Kleinberg","year":"1998","unstructured":"Kleinberg, J., Tardos, E.: Approximations for the disjoint paths problem in high-diameter planar networks. Journal of Computers and System Sciences\u00a057(1), 61\u201373 (1998)","journal-title":"Journal of Computers and System Sciences"},{"key":"28_CR15","doi-asserted-by":"crossref","unstructured":"Lee, J.R., Sidiropoulos, A.: Genus and the geometry of the cut graph. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 193\u2013201. Society for Industrial and Applied Mathematics (2010)","DOI":"10.1137\/1.9781611973075.18"},{"issue":"6","key":"28_CR16","doi-asserted-by":"publisher","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. Journal of the ACM\u00a046(6), 787\u2013832 (1999)","journal-title":"Journal of the ACM"},{"key":"28_CR17","first-page":"153","volume":"103","author":"N. Robertson","year":"1985","unstructured":"Robertson, N., Seymour, P.D.: Graph minors: a survey. Surveys in Combinatorics\u00a0103, 153\u2013171 (1985)","journal-title":"Surveys in Combinatorics"},{"issue":"1","key":"28_CR18","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0095-8956(03)00042-X","volume":"89","author":"N. Robertson","year":"2003","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XVI. Excluding a non-planar graph. Journal of Combinatorial Theory, Series B\u00a089(1), 43\u201376 (2003)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"28_CR19","doi-asserted-by":"crossref","unstructured":"Seguin-Charbonneau, L., Shepherd, F.B.: Maximum edge-disjoint paths in planar graphs with congestion 2. In: Proc. of IEEE FOCS, pp. 200\u2013209 (2011)","DOI":"10.1109\/FOCS.2011.30"},{"key":"28_CR20","unstructured":"Shmoys, D.: Cut problems and their application to divide-and-conquer. In: Approximation Algorithms for NP-Hard Problems. PWS series in computer science. PWS Pub. Co. (1997)"},{"issue":"2","key":"28_CR21","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0020-0190(93)90228-2","volume":"47","author":"\u00c9. Tardos","year":"1993","unstructured":"Tardos, \u00c9., Vazirani, V.V.: Improved bounds for the max-flow min-multicut ratio for planar and K\n                  \n                    r,r\n                  -free graphs. Information Processing Letters\u00a047(2), 77\u201380 (1993)","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-39206-1_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T09:30:23Z","timestamp":1557912623000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-39206-1_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642392054","9783642392061"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39206-1_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}