{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:09:36Z","timestamp":1763467776055,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2006,9,1]],"date-time":"2006-09-01T00:00:00Z","timestamp":1157068800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2006,9]]},"abstract":"<jats:p>\n            We show that there is no log\n            <jats:sup>\u2153 \u2212 \u03b5<\/jats:sup>\n            <jats:italic>M<\/jats:italic>\n            approximation for the undirected Edge-Disjoint Paths problem unless\n            <jats:italic>NP<\/jats:italic>\n            \u2286\n            <jats:italic>ZPTIME<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              polylog(\n              <jats:italic>n<\/jats:italic>\n              )\n            <\/jats:sup>\n            ), where\n            <jats:italic>M<\/jats:italic>\n            is the size of the graph and \u03b5 is any positive constant. This hardness result also applies to the undirected All-or-Nothing Multicommodity Flow problem and the undirected Node-Disjoint Paths problem.\n          <\/jats:p>","DOI":"10.1145\/1183907.1183910","type":"journal-article","created":{"date-parts":[[2007,1,16]],"date-time":"2007-01-16T19:38:29Z","timestamp":1168976309000},"page":"745-761","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Logarithmic hardness of the undirected edge-disjoint paths problem"],"prefix":"10.1145","volume":"53","author":[{"given":"Matthew","family":"Andrews","sequence":"first","affiliation":[{"name":"Bell Labs, Murray Hill, New Jersey"}]},{"given":"Lisa","family":"Zhang","sequence":"additional","affiliation":[{"name":"Bell Labs, Murray Hill, New Jersey"}]}],"member":"320","published-online":{"date-parts":[[2006,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.32"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.41"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060633"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060632"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132592"},{"volume-title":"Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms ACM","author":"Aumann Y.","key":"e_1_2_1_6_1","unstructured":"Aumann , Y. , and Rabani , Y . 1995. Improved bounds for all optical routing . In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms ACM , New York. 567--576.]] Aumann, Y., and Rabani, Y. 1995. Improved bounds for all optical routing. In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms ACM, New York. 567--576.]]"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Azar Y. and Regev O. 2001. Strongly polynomial algorithms for the unsplittable flow problem. In Integer Programming and Combinatorial Optimization. PP. 15--29.]]   Azar Y. and Regev O. 2001. Strongly polynomial algorithms for the unsplittable flow problem. In Integer Programming and Combinatorial Optimization. PP. 15--29.]]","DOI":"10.1007\/3-540-45535-3_2"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.25.2.255.12228"},{"volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Chekuri C.","key":"e_1_2_1_9_1","unstructured":"Chekuri , C. , and Khanna , S . 2003. Edge-disjoint paths revisited . In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM , New York.]] Chekuri, C., and Khanna, S. 2003. Edge-disjoint paths revisited. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York.]]"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007383"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132621"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a007"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050043"},{"key":"e_1_2_1_14_1","first-page":"251","article-title":"Regul\u00e4re graphen gegebener Taillenweite mit minimaler Knotenzahl","volume":"12","author":"Erd\u00f6s P.","year":"1963","unstructured":"Erd\u00f6s , P. , and Sachs , H. 1963 . Regul\u00e4re graphen gegebener Taillenweite mit minimaler Knotenzahl . Wiss. Z. Uni. Halle-Wittenburg (Math. Nat.) 12 , 251 -- 257 .]] Erd\u00f6s, P., and Sachs, H. 1963. Regul\u00e4re graphen gegebener Taillenweite mit minimaler Knotenzahl. Wiss. Z. Uni. Halle-Wittenburg (Math. Nat.) 12, 251--257.]]","journal-title":"Wiss. Z. Uni. Halle-Wittenburg (Math. Nat.)"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226652"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90009-2"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523685"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00066-7"},{"key":"e_1_2_1_19_1","first-page":"85","volume-title":"Miller and J. W. Thatcher","author":"Karp R. M.","year":"1972","unstructured":"Karp , R. M. 1972 . Reducibility among combinatorial problems. In Complexity of Computer Computations, R. E . Miller and J. W. Thatcher , Eds , pp. 85 -- 103 .]] Karp, R. M. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, Eds, pp. 85--103.]]"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875508"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276867"},{"key":"e_1_2_1_23_1","first-page":"52","volume-title":"Proceedings of the 36th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press","author":"Kleinberg J.","unstructured":"Kleinberg , J. , and Tardos , E . 1995. Disjoint paths in densely embedded graphs . In Proceedings of the 36th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press , Los Alamitos, CA , pp. 52 -- 61 .]] Kleinberg, J., and Tardos, E. 1995. Disjoint paths in densely embedded graphs. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, pp. 52--61.]]"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1579"},{"key":"e_1_2_1_25_1","first-page":"426","volume-title":"Proceedings of the 38th Annual Symposium on Foundations of Computer Science","author":"Kolliopoulos S.","unstructured":"Kolliopoulos , S. , and Stein , C . 1997. Improved approximation algorithms for unsplittable flow problems . In Proceedings of the 38th Annual Symposium on Foundations of Computer Science ( Miami Beach, FL, Oct.). IEEE Computer Society Press, Los Alamitos, CA , pp. 426 -- 435 .]] Kolliopoulos, S., and Stein, C. 1997. Improved approximation algorithms for unsplittable flow problems. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science (Miami Beach, FL, Oct.). IEEE Computer Society Press, Los Alamitos, CA, pp. 426--435.]]"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Kolliopoulos S. and Stein C. 1998. Approximating disjoint-path problems using greedy algorithms and packet integer programs. In Integer Programming and Combinatorial Optimization.]]  Kolliopoulos S. and Stein C. 1998. Approximating disjoint-path problems using greedy algorithms and packet integer programs. In Integer Programming and Combinatorial Optimization.]]","DOI":"10.1007\/3-540-69346-7_12"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1661"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579324"},{"key":"e_1_2_1_30_1","unstructured":"Robertson N. and Seymour P. D. 1990. 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. Springer-Verlag New York.]]  Robertson N. and Seymour P. D. 1990. 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. Springer-Verlag New York.]]"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335329"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/795663.796366"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380839"},{"volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Varadarajan K.","key":"e_1_2_1_34_1","unstructured":"Varadarajan , K. , and Venkataraman , G . 2004. Graph decomposition and a greedy algorithm for edge-disjoint paths . In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM , New York.]] Varadarajan, K., and Venkataraman, G. 2004. Graph decomposition and a greedy algorithm for edge-disjoint paths. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York.]]"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1183907.1183910","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1183907.1183910","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:06:35Z","timestamp":1750259195000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1183907.1183910"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,9]]},"references-count":33,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2006,9]]}},"alternative-id":["10.1145\/1183907.1183910"],"URL":"https:\/\/doi.org\/10.1145\/1183907.1183910","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2006,9]]},"assertion":[{"value":"2006-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}