{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T16:59:08Z","timestamp":1709830748733},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2007,11,21]],"date-time":"2007-11-21T00:00:00Z","timestamp":1195603200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2009,7]]},"DOI":"10.1007\/s00453-007-9129-z","type":"journal-article","created":{"date-parts":[[2007,11,20]],"date-time":"2007-11-20T16:04:17Z","timestamp":1195574657000},"page":"400-412","source":"Crossref","is-referenced-by-count":10,"title":["A Note on Multiflows and Treewidth"],"prefix":"10.1007","volume":"54","author":[{"given":"Chandra","family":"Chekuri","sequence":"first","affiliation":[]},{"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[]},{"given":"F. Bruce","family":"Shepherd","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,11,21]]},"reference":[{"key":"9129_CR1","series-title":"Contemporary Mathematics","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1090\/conm\/147\/01199","volume-title":"Graph Structure Theory, Proceedings of the Joint Summer Research Conference on Graph Minors","author":"K. Abrahamson","year":"1993","unstructured":"Abrahamson, K., Fellows, M.: Finite automata, bounded treewidth and well-quasiordering. In: Robertson, N., Seymour, P. (eds.) Graph Structure Theory, Proceedings of the Joint Summer Research Conference on Graph Minors, Seattle, June 1991. Contemporary Mathematics, vol.\u00a0147, pp. 539\u2013564. American Mathematical Society, Providence (1993)"},{"issue":"5","key":"9129_CR2","doi-asserted-by":"crossref","first-page":"745","DOI":"10.1145\/1183907.1183910","volume":"53","author":"M. Andrews","year":"2006","unstructured":"Andrews, M., Zhang, L.: Logarithmic hardness of the undirected edge-disjoint paths problem. JACM 53(5), 745\u2013761 (2006). Preliminary version in Proc. of ACM STOC, pp.\u00a0276\u2013283, 2005","journal-title":"JACM"},{"key":"9129_CR3","doi-asserted-by":"crossref","unstructured":"Andrews, M., Chuzhoy, J., Khanna, S., Zhang, L.: Hardness of the undirected edge-disjoint paths problem with congestion. In: Proc. of IEEE FOCS, pp.\u00a0226\u2013244, 2005","DOI":"10.1109\/SFCS.2005.41"},{"key":"9129_CR4","doi-asserted-by":"crossref","unstructured":"Arora, S., Rao, S., Vazirani, U.: Expander flows, geometric embeddings, and graph Partitioning. In: Proc. of ACM STOC, pp.\u00a0222\u2013231, 2004","DOI":"10.1145\/1007352.1007355"},{"key":"9129_CR5","doi-asserted-by":"crossref","unstructured":"Arora, S., Lee, J.R., Naor, A.: Euclidean distortion and the sparsest cut. In: Proc. of ACM STOC, pp.\u00a0553\u2013562, 2005","DOI":"10.1145\/1060590.1060673"},{"issue":"1","key":"9129_CR6","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1137\/S0097539794285983","volume":"27","author":"Y. Aumann","year":"1998","unstructured":"Aumann, Y., Rabani, Y.: An O(log\u2009k) approximate min-cut max-flow theorem and approximation algorithm. SIAM J. Computing 27(1), 291\u2013301 (1998)","journal-title":"SIAM J. Computing"},{"key":"9129_CR7","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25, 1305\u2013317 (1996). Preliminary version in Proc. of ACM STOC, 1993","journal-title":"SIAM J. Comput."},{"key":"9129_CR8","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Khanna, S., Shepherd, F.B.: The all-or-nothing multicommodity flow problem. In: Proc. of ACM STOC, pp.\u00a0156\u2013165, 2004","DOI":"10.1145\/1007352.1007383"},{"key":"9129_CR9","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Khanna, S., Shepherd, F.B.: Edge disjoint paths in planar graphs. In: Proc. of IEEE FOCS, pp.\u00a071\u201380, 2004","DOI":"10.1109\/FOCS.2004.27"},{"key":"9129_CR10","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Khanna, S., Shepherd, F.B.: Multicommodity flow, well-linked terminals, and routing problems. In: Proc. of ACM STOC, pp.\u00a0183\u2013192, 2005","DOI":"10.1145\/1060590.1060618"},{"key":"9129_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 $O(\\sqrt{n})$ approximation and integrality gap for disjoint paths and unsplittable flow. Theory Comput. 2, 137\u2013146 (2006)","journal-title":"Theory Comput."},{"key":"9129_CR12","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Khanna, S., Shepherd, F.B.: Edge-disjoint paths in planar graphs with constant congestion. In: Proc. of ACM STOC, pp.\u00a0757\u2013766, 2006","DOI":"10.1145\/1132516.1132621"},{"key":"9129_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 (2007). Preliminary version in Proc. of ICALP, 2003","DOI":"10.1145\/1273340.1273343"},{"key":"9129_CR14","doi-asserted-by":"crossref","unstructured":"Feige, U., Hajiaghayi, M., Lee, J.: Improved approximation algorithms for minimum-weight vertex separators. SIAM J. Comput. (to appear). Preliminary version in Proc. of ACM STOC, pp.\u00a0563\u2013572, 2005","DOI":"10.1145\/1060590.1060674"},{"key":"9129_CR15","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)"},{"issue":"1","key":"9129_CR16","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF02523685","volume":"18","author":"N. Garg","year":"1997","unstructured":"Garg, N., Vazirani, V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18(1), 3\u201320 (1997)","journal-title":"Algorithmica"},{"key":"9129_CR17","unstructured":"Geelen, J., Gerards, B., Whittle, G.: Tangles, tree-decompositions, and grids in matroids. Technical Research Report 04-5, School of Mathematical and Computing Sciences, Victoria Univ., Wellington, New Zealand"},{"key":"9129_CR18","doi-asserted-by":"crossref","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 \u2113 1-embeddings of graphs. Combinatorica 24, 233\u2013269 (2004). Preliminary version in Proc. of IEEE FOCS, 1999","journal-title":"Combinatorica"},{"key":"9129_CR19","doi-asserted-by":"crossref","unstructured":"Indyk, P., Sidiropoulos, A.: Probabilistic embeddings of bounded genus graphs into planar graphs. In: Proc. of ACM SoCG, pp.\u00a0204\u2013209, 2007","DOI":"10.1145\/1247069.1247107"},{"key":"9129_CR20","unstructured":"Klein, P., Plotkin, S., Rao, S.: Planar graphs, multicommodity flow, and network decomposition. In: Proc. of ACM STOC, pp.\u00a0682\u2013690, 1993"},{"key":"9129_CR21","unstructured":"Kleinberg, J.M.: Approximation algorithms for disjoint paths problems. PhD thesis, MIT, Cambridge, MA (1996)"},{"key":"9129_CR22","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.M.: An approximation algorithm for the disjoint paths problem in even-degree planar graphs. In: Proc. of IEEE FOCS, pp.\u00a0627\u2013636, 2005","DOI":"10.1109\/SFCS.2005.18"},{"key":"9129_CR23","volume-title":"Handbook on Approximation Algorithms and Metaheuristics","author":"S.G. Kolliopoulos","year":"2007","unstructured":"Kolliopoulos, S.G.: Edge disjoint paths and unsplittable flow. In: Handbook on Approximation Algorithms and Metaheuristics. Chapman Hall\/CRC Press, London\/Boca Raton (2007)"},{"key":"9129_CR24","unstructured":"Kolliopoulos, S.G., Stein, C.: Approximating disjoint-path problems using greedy algorithms and packing integer programs. Math. Program. A (99), 63\u201387 (2004). Preliminary version in Proc. of IPCO, 1998"},{"key":"9129_CR25","unstructured":"Kolman, P., Scheideler, C.: Improved bounds for the unsplittable flow problem. In: Proc. of ACM-SIAM SODA, pp.\u00a0184\u2013193, 2002"},{"issue":"4","key":"9129_CR26","doi-asserted-by":"crossref","first-page":"839","DOI":"10.1007\/s00039-005-0527-6","volume":"15","author":"R. Krauthgamer","year":"2005","unstructured":"Krauthgamer, R., Lee, J., Mendel, M., Naor, A.: Measured descent: a new embedding method for finite metrics. Geom. Funct. Anal. 15(4), 839\u2013858 (2005). Preliminary version in Proc. of IEEE FOCS, 2004","journal-title":"Geom. Funct. Anal."},{"issue":"6","key":"9129_CR27","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. JACM 46(6), 787\u2013832 (1999). Preliminary version in Proc. of IEEE FOCS, 1988","journal-title":"JACM"},{"issue":"2","key":"9129_CR28","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). Preliminary version in Proc. of IEEE FOCS, 1994","journal-title":"Combinatorica"},{"key":"9129_CR29","doi-asserted-by":"crossref","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. Comb. Theory Ser. B 31, 75\u201381 (1981)","journal-title":"J. Comb. Theory Ser. B"},{"key":"9129_CR30","doi-asserted-by":"crossref","unstructured":"Rabinovich, Y.: On average distortion of embedding metrics into the line and into \u2113 1. In: Proc. of ACM STOC, pp.\u00a0456\u2013462, 2003","DOI":"10.1145\/780542.780609"},{"key":"9129_CR31","doi-asserted-by":"crossref","unstructured":"Rao, S.: Small distortion and volume preserving embeddings for planar and Euclidean metrics. In: Proc. of ACM SoCG, pp.\u00a0300\u2013306, 1999","DOI":"10.1145\/304893.304983"},{"issue":"1","key":"9129_CR32","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"35","author":"N. Robertson","year":"1983","unstructured":"Robertson, N., Seymour, P.D.: Graph Minors. I. Excluding a forest. J. Comb. Theory Ser. B 35(1), 39\u201361 (1983)","journal-title":"J. Comb. Theory Ser. B"},{"key":"9129_CR33","volume-title":"Paths, Flows and VLSI-Layout","author":"N. Robertson","year":"1990","unstructured":"Robertson, N., Seymour, P.D.: Outline of a disjoint paths algorithm. In: Korte, B., Lov\u00e1sz, L., Pr\u00f6mel, H.J., Schrijver, A. (eds.) Paths, Flows and VLSI-Layout. Springer, Berlin (1990)"},{"key":"9129_CR34","doi-asserted-by":"crossref","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. J. Comb. Theory Ser. B 89, 43\u201376 (2003)","journal-title":"J. Comb. Theory Ser. B"},{"key":"9129_CR35","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1006\/jctb.1994.1073","volume":"62","author":"N. Robertson","year":"1994","unstructured":"Robertson, N., Seymour, P.D., Thomas, R.: Quickly Excluding a Planar Graph. J. Comb. Theory Ser. B 62, 323\u2013348 (1994)","journal-title":"J. Comb. Theory Ser. B"},{"key":"9129_CR36","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003)"},{"key":"9129_CR37","unstructured":"Sidiropoulos, A.: Personal communication (November 2006)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9129-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9129-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9129-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:01Z","timestamp":1559137501000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9129-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,11,21]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,7]]}},"alternative-id":["9129"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9129-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,11,21]]}}}