{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T11:30:58Z","timestamp":1742988658074,"version":"3.40.3"},"publisher-location":"Boston, MA","reference-count":18,"publisher":"Springer US","isbn-type":[{"type":"print","value":"9780387307701"},{"type":"electronic","value":"9780387301624"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-0-387-30162-4_244","type":"book-chapter","created":{"date-parts":[[2008,6,26]],"date-time":"2008-06-26T18:35:29Z","timestamp":1214505329000},"page":"551-554","source":"Crossref","is-referenced-by-count":0,"title":["Multicommodity Flow, Well-linked Terminals and Routing Problems"],"prefix":"10.1007","author":[{"given":"Chandra","family":"Chekuri","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"244_CR1_244","doi-asserted-by":"crossref","unstructured":"Andrews, M., Chuzhoy, J., Khanna, S., Zhang, L.: Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion. Proc. of IEEE FOCS, 2005, pp.\u00a0226\u2013244","DOI":"10.1145\/1060590.1060632"},{"issue":"1","key":"244_CR2_244","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/s00453-005-1172-z","volume":"44","author":"Y. Azar","year":"2006","unstructured":"Azar, Y., Regev, O.: Combinatorial algorithms for the unsplittable flow problem. Algorithmica 44(1), 49\u201366 (2006). Preliminary version in Proc. of IPCO 2001","journal-title":"Algorithmica"},{"key":"244_CR3_244","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Khanna, S., Shepherd, F.B.: A\u00a0note on multiflows and treewidth. Algorithmica, published online (2007)","DOI":"10.1007\/s00453-007-9129-z"},{"key":"244_CR4_244","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 $$ O(\\sqrt{n}) $$ approximation and integrality gap for disjoint paths and UFP. Theor. Comput. 2, 137\u2013146 (2006)","journal-title":"Theor. Comput."},{"key":"244_CR5_244","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Khanna, S., Shepherd, F.B.: Edge-Disjoint Paths in Planar Graphs with Constant Congestion. Proc. ACM STOC, pp.\u00a0757\u2013766 (2006)","DOI":"10.1145\/1132516.1132621"},{"key":"244_CR6_244","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Khanna, S., Shepherd, F.B.: Multicommodity flow, well-linked terminals, and routing problems. Proc. ACM STOC, pp.\u00a0183\u2013192 (2005)","DOI":"10.1145\/1060590.1060618"},{"key":"244_CR7_244","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Khanna, S., Shepherd, F.B.: The All-or-Nothing Multicommodity Flow Problem. Proc. ACM STOC, pp.\u00a0156\u2013165 (2004)","DOI":"10.1145\/1007352.1007383"},{"key":"244_CR8_244","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Khanna, S., Shepherd, F.B.: Edge Disjoint Paths in Planar Graphs. Proc. of IEEE FOCS, 2004, pp.\u00a071\u201380","DOI":"10.1109\/FOCS.2004.27"},{"key":"244_CR9_244","first-page":"49","volume-title":"Paths, Flows and VLSI-Layout","author":"A. Frank","year":"1990","unstructured":"Frank, A.: Packing paths, cuts, and circuits\u00a0\u2013 a\u00a0survey. In: Korte, B., Lov\u00e1sz, L., Pr\u00f6mel H.J., Schrijver A. (eds.) Paths, Flows and VLSI-Layout, pp.\u00a049\u2013100. Springer, Berlin (1990)"},{"issue":"1","key":"244_CR10_244","doi-asserted-by":"publisher","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). Preliminary version appeared in Proc. ICALP 1993","journal-title":"Algorithmica"},{"key":"244_CR11_244","first-page":"473","volume":"67","author":"V. Guruswami","year":"2003","unstructured":"Guruswami, V., Khanna, S., Rajaraman, R., Shepherd, F.B., Yannakakis, M.: Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems. J. CSS 67, 473\u2013496 (2003). Preliminary version in Proc. of ACM STOC 1999","journal-title":"J. CSS"},{"key":"244_CR12_244","unstructured":"Kleinberg, J.M.: Approximation algorithms for disjoint paths problems. Ph.\u202fD. thesis, MIT, Cambridge, MA (1996)"},{"key":"244_CR13_244","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.M.: An Approximation Algorithm for the Disjoint Paths Problem in Even-Degree Planar Graphs. Proc. of IEEE FOCS, 2005, pp.\u00a0627\u2013636","DOI":"10.1109\/SFCS.2005.18"},{"key":"244_CR14_244","doi-asserted-by":"crossref","unstructured":"Kolliopoulos, S.G.: Edge Disjoint Paths and Unsplittable Flow. In: Handbook on Approximation Algorithms and Metaheuristics, Chapman & Hall\/CRC Press Computer & Science Series, vol 13. Chapman Hall\/CRC Press, May 2007","DOI":"10.1201\/9781420010749.ch57"},{"key":"244_CR15_244","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/s10107-002-0370-6","volume":"99","author":"S.G. Kolliopoulos","year":"2004","unstructured":"Kolliopoulos, S.G., Stein, C.: Approximating Disjoint-Path Problems Using Greedy Algorithms and Packing Integer Programs. Math. Program. A\u00a099, 63\u201387 (2004). Preliminary version in Proc. of IPCO 1998","journal-title":"Math. Program. A"},{"issue":"1","key":"244_CR16_244","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.\u00a0Comb. Theor. B 63(1), 65\u2013110 (1995)","journal-title":"J. Comb. Theor. B"},{"key":"244_CR17_244","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003)"},{"key":"244_CR18_244","doi-asserted-by":"crossref","unstructured":"Srinivasan, A.: Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems. Proc. IEEE FOCS, 1997, pp.\u00a0416\u2013425","DOI":"10.1109\/SFCS.1997.646130"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-30162-4_244","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,30]],"date-time":"2025-01-30T21:32:29Z","timestamp":1738272749000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-30162-4_244"}},"subtitle":["2005; Chekuri, Khanna, Shepherd"],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387307701","9780387301624"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4_244","relation":{},"subject":[],"published":{"date-parts":[[2008]]}}}