{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:13:55Z","timestamp":1763468035326,"version":"3.38.0"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2010,9,1]],"date-time":"2010-09-01T00:00:00Z","timestamp":1283299200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2010,9]]},"DOI":"10.1007\/s00493-010-2455-9","type":"journal-article","created":{"date-parts":[[2011,3,25]],"date-time":"2011-03-25T21:24:05Z","timestamp":1301088245000},"page":"485-520","source":"Crossref","is-referenced-by-count":39,"title":["Inapproximability of Edge-Disjoint Paths and low congestion routing on undirected graphs"],"prefix":"10.1007","volume":"30","author":[{"given":"Matthew","family":"Andrews","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Julia","family":"Chuzhoy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkatesan","family":"Guruswami","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kunal","family":"Talwar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lisa","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,3,13]]},"reference":[{"key":"2455_CR1","doi-asserted-by":"crossref","unstructured":"M. Andrews: Hardness of buy-at-bulk network design, in: Proceedings of the 45th Annual Symposium on Foundations of Computer Science, pages 115\u2013124, Rome, Italy, October 2004.","DOI":"10.1109\/FOCS.2004.32"},{"key":"2455_CR2","doi-asserted-by":"crossref","unstructured":"M. Andrews, J. Chuzhoy, S. Khanna and L. Zhang: Hardness of the undirected edge-disjoint paths problem with congestion, in: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pages 226\u2013244, 2005.","DOI":"10.1109\/SFCS.2005.41"},{"key":"2455_CR3","doi-asserted-by":"crossref","unstructured":"M. Andrews and L. Zhang: Hardness of the undirected edge-disjoint paths problem, in: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pages 276\u2013283, 2005.","DOI":"10.1145\/1060590.1060632"},{"key":"2455_CR4","doi-asserted-by":"crossref","unstructured":"M. Andrews and L. Zhang: Hardness of the undirected congestion minimization problem, in: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pages 284\u2013293, 2005.","DOI":"10.1145\/1060590.1060633"},{"key":"2455_CR5","unstructured":"M. Andrews and L. Zhang: Hardness of the edge-disjoint paths problem with congestion, Manuscript, 2005. Available at: ]http:\/\/ect.bell-labs.com\/who\/dmandrews\/publications\/edp-congestion.ps ."},{"key":"2455_CR6","doi-asserted-by":"crossref","unstructured":"M. Andrews and L. Zhang: Logarithmic hardness of the directed congestion minimization problem, in: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pages 517\u2013526, 2006.","DOI":"10.1145\/1132516.1132592"},{"issue":"1","key":"2455_CR7","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1137\/S0097539794285983","volume":"27","author":"Y. Aumann","year":"1998","unstructured":"Y. Aumann and Y. Rabani: An O(log k) approximate min-cut max-flow theorem and approximation algorithm, SIAM Journal on Computing 27(1) (1998), 291\u2013301.","journal-title":"SIAM Journal on Computing"},{"key":"2455_CR8","doi-asserted-by":"crossref","unstructured":"Y. Azar and O. Regev: Strongly polynomial algorithms for the unsplittable flow problem, in: Proceedings of the 8th Integer Programming and Combinatorial Optimization Conference, pages 15\u201329, 2001.","DOI":"10.1007\/3-540-45535-3_2"},{"issue":"2","key":"2455_CR9","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1287\/moor.25.2.255.12228","volume":"25","author":"A. Baveja","year":"2000","unstructured":"A. Baveja and A. Srinivasan: Approximation algorithms for disjoint paths and related routing and packing problems, Mathematics of Operations Research 25(2) (2000), 255\u2013280.","journal-title":"Mathematics of Operations Research"},{"key":"2455_CR10","doi-asserted-by":"crossref","unstructured":"C. Chekuri, S. Khanna and F. B. Shepherd: The all-or-nothing multicommodity flow problem, in: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pages 156\u2013165, 2004.","DOI":"10.1145\/1007352.1007383"},{"key":"2455_CR11","doi-asserted-by":"crossref","unstructured":"C. Chekuri, S. Khanna and F. B. Shepherd: Edge-disjoint paths in planar graphs with constant congestion, in: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pages 757\u2013766, 2006.","DOI":"10.1145\/1132516.1132621"},{"key":"2455_CR12","doi-asserted-by":"crossref","unstructured":"C. Chekuri, S. Khanna and F. B. Shepherd: Multicommodity flow, well-linked terminals, and routing problems; in: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pages 183\u2013192, 2005.","DOI":"10.1145\/1060590.1060618"},{"key":"2455_CR13","doi-asserted-by":"crossref","first-page":"137","DOI":"10.4086\/toc.2006.v002a007","volume":"2","author":"C. Chekuri","year":"2006","unstructured":"C. Chekuri, S. Khanna and F. B. Shepherd: An O( % MathType!MTEF!2!1!+- % feaagaart1ev2aaatCvAUfKttLearuqr1ngBPrgarmWu51MyVXgatC % vAUfeBSjuyZL2yd9gzLbvyNv2CaeHbd9wDYLwzYbItLDharyavP1wz % ZbItLDhis9wBH5garqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbb % L8F4rqqrFfpeea0xe9Lq-Jc9vqaqpepm0xbba9pwe9Q8fs0-yqaqpe % pae9pg0FirpepeKkFr0xfr-xfr-xb9adbaqaaeGaciGaaiaabeqaam % aaeaqbaaGcbaWaaOaaaeaacqWGUbGBaSqabaaaaa!3C4B! $$ \\sqrt n $$ )-approximation and integrality gap for disjoint paths and UFP, Theory of Computing 2 (2006), 137\u2013146.","journal-title":"Theory of Computing"},{"key":"2455_CR14","unstructured":"C. Chekuri and S. Khanna: Edge disjoint paths revisited, in: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 628\u2013637, 2003."},{"key":"2455_CR15","unstructured":"C. Chekuri, M. Mydlarz and F. B. Shepherd: Multicommodity demand flow in a tree and packing integer programs, ACM Transactions on Algorithms 3(3) (2007), Art.no. 27."},{"key":"2455_CR16","unstructured":"J. Chuzhoy and S. Khanna: New hardness results for undirected edge disjoint paths, Manuscript, 2005. Available at: http:\/\/ttic.uchicago.edu\/~cjulia\/papers\/edpc.pdf ."},{"key":"2455_CR17","doi-asserted-by":"crossref","unstructured":"J. Chuzhoy, V. Guruswami, S. Khanna and K. Talwar: Hardness of routing with congestion in directed graphs, in: Proceedings of 39th Annual ACM Symposium on Theory of Computing, pages 165\u2013178, 2007.","DOI":"10.1145\/1250790.1250816"},{"key":"2455_CR18","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1137\/S0895480100380458","volume":"18","author":"L. Engebretsen","year":"2004","unstructured":"L. Engebretsen: The nonapproximability of non-boolean predicates, SIAM Journal on Discrete Mathematics 18 (2004), 114\u2013129.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"2455_CR19","first-page":"251","volume":"12","author":"P. Erd\u0151s","year":"1963","unstructured":"P. Erd\u0151s and H. Sachs: Regul\u00e4re Graphen gegebener Taillenweite mit minimaler Knotenzahl, Wiss. Z. Uni. Halle-Wittenburg (Math. Nat.) 12 (1963), 251\u2013257.","journal-title":"Wiss. Z. Uni. Halle-Wittenburg (Math. Nat.)"},{"key":"2455_CR20","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1016\/0095-8956(85)90046-2","volume":"2","author":"A. Frank","year":"1985","unstructured":"A. Frank: Edge-disjoint paths in planar graphs, J. of Combinatorial Theory, Ser. B 2 (1985), 164\u2013178.","journal-title":"J. of Combinatorial Theory, Ser. B"},{"issue":"2","key":"2455_CR21","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S. Fortune","year":"1980","unstructured":"S. Fortune, J. Hopcroft and J. Wyllie: The directed subgraph homeomorphism problem, Theoretical Computer Science 10(2) (1980), 111\u2013121.","journal-title":"Theoretical Computer Science"},{"key":"2455_CR22","doi-asserted-by":"crossref","unstructured":"Z. Friggstad and M. R. Salavatipour: Approximability of packing disjoint cycles, in: Proceedings of 18th International Symposium on Algorithms and Computation, pages 304\u2013315, 2007.","DOI":"10.1007\/978-3-540-77120-3_28"},{"key":"2455_CR23","unstructured":"M. R. Garey and D. S. Johnson: Computers and intractability: A guide to the theory of NP-completeness; Freeman, 1979."},{"issue":"1","key":"2455_CR24","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF02523685","volume":"18","author":"N. Garg","year":"1997","unstructured":"N. Garg, V. Vazirani and M. Yannakakis: Primal-dual approximation algorithms for integral flow and multicut in trees, Algorithmica 18(1) (1997), 3\u201320.","journal-title":"Algorithmica"},{"issue":"3","key":"2455_CR25","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1016\/S0022-0000(03)00066-7","volume":"67","author":"V. Guruswami","year":"2003","unstructured":"V. Guruswami, S. Khanna, R. Rajaraman, F. B. Shepherd and M. Yannakakis: Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems, J. Comput. Syst. Sci. 67(3) (2003), 473\u2013496.","journal-title":"J. Comput. Syst. Sci."},{"key":"2455_CR26","unstructured":"V. Guruswami and K. Talwar: Hardness of low congestion routing in undirected graphs, Manuscript, 2005."},{"issue":"7","key":"2455_CR27","doi-asserted-by":"crossref","first-page":"119","DOI":"10.4086\/toc.2005.v001a007","volume":"1","author":"J. H\u00e5stad","year":"2005","unstructured":"J. H\u00e5stad and S. Khot: Query efficient PCPs with perfect completeness, Theory of Computing 1(7) (2005), 119\u2013148.","journal-title":"Theory of Computing"},{"issue":"2","key":"2455_CR28","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1002\/rsa.10068","volume":"22","author":"J. H\u00e5stad","year":"2003","unstructured":"J. H\u00e5stad and A. Wigderson: Simple analysis of graph tests for linearity and PCP, Random Structures and Algorithms 22(2) (2003), 139\u2013160.","journal-title":"Random Structures and Algorithms"},{"key":"2455_CR29","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1006\/jcss.1998.1579","volume":"57","author":"J. M. Kleinberg","year":"1998","unstructured":"J. M. Kleinberg and \u00c9. Tardos: Approximations for the disjoint paths problem in high-diameter planar networks, Journal of Computer and System Sciences 57 (1998), 61\u201373.","journal-title":"Journal of Computer and System Sciences"},{"key":"2455_CR30","doi-asserted-by":"crossref","unstructured":"J. M. Kleinberg and \u00c9. Tardos: Disjoint paths in densely embedded graphs, in: Proceedings of the 36th Annual Symposium on Foundations of Computer Science, page 52, 1995.","DOI":"10.1109\/SFCS.1995.492462"},{"key":"2455_CR31","volume-title":"Approximation algorithms for disjoint paths problems","author":"J. M. Kleinberg","year":"1996","unstructured":"J. M. Kleinberg: Approximation algorithms for disjoint paths problems, PhD thesis, MIT, Cambridge, MA, 1996."},{"key":"2455_CR32","doi-asserted-by":"crossref","unstructured":"S. G. Kolliopoulos and C. Stein: Approximating disjoint-path problems using greedy algorithms and packing integer programs, in: Proceedings of the Conference on Integer Programming and Combinatorial Approximation, pages 153\u2013168, 1998.","DOI":"10.1007\/3-540-69346-7_12"},{"key":"2455_CR33","unstructured":"M. Krivelevich, Z. Nutov and R. Yuster: Approximation algorithms for cycle packing problems, in: Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, pages 556\u2013561, 2005."},{"issue":"4","key":"2455_CR34","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P. Raghavan","year":"1987","unstructured":"P. Raghavan and C. D. Thompson: Randomized rounding: A technique for provably good algorithms and algorithmic proofs; Combinatorica 7(4) (1987), 365\u2013374.","journal-title":"Combinatorica"},{"issue":"3","key":"2455_CR35","doi-asserted-by":"crossref","first-page":"763","DOI":"10.1137\/S0097539795280895","volume":"27","author":"R. Raz","year":"1998","unstructured":"R. Raz: A parallel repetition theorem, SIAM Journal on Computing 27(3) (1998), 763\u2013803.","journal-title":"SIAM Journal on Computing"},{"key":"2455_CR36","first-page":"267","volume-title":"Paths, Flows and VLSI-Layout","author":"N. Robertson","year":"1990","unstructured":"N. Robertson and P. D. Seymour: An outline of a disjoint paths algorithm, in: Paths, Flows and VLSI-Layout (B. Korte, L. Lov\u00e1sz, H. J. Pr\u00f6mel and A. Schrijver, eds.), pages 267\u2013292, Springer-Verlag, Berlin, 1990."},{"key":"2455_CR37","doi-asserted-by":"crossref","unstructured":"A. Samorodnitsky and L. Trevisan: A PCP characterization of NP with optimal amortized query complexity, in: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, pages 191\u2013199, 2000.","DOI":"10.1145\/335305.335329"},{"key":"2455_CR38","doi-asserted-by":"crossref","unstructured":"A. Srinivasan: Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems; in: Proceedings of the 38th Symposium on Foundations of Computer Science, pages 416\u2013425, 1997.","DOI":"10.1109\/SFCS.1997.646130"},{"key":"2455_CR39","unstructured":"K. Varadarajan and G. Venkataraman: Graph decomposition and a greedy algorithm for edge-disjoint paths, in: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 379\u2013380, 2004."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-010-2455-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-010-2455-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-010-2455-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,4]],"date-time":"2025-03-04T18:04:43Z","timestamp":1741111483000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-010-2455-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9]]},"references-count":39,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2010,9]]}},"alternative-id":["2455"],"URL":"https:\/\/doi.org\/10.1007\/s00493-010-2455-9","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"type":"print","value":"0209-9683"},{"type":"electronic","value":"1439-6912"}],"subject":[],"published":{"date-parts":[[2010,9]]}}}