{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T14:40:06Z","timestamp":1736520006269,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540359043"},{"type":"electronic","value":"9783540359050"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11786986_19","type":"book-chapter","created":{"date-parts":[[2006,6,28]],"date-time":"2006-06-28T10:46:45Z","timestamp":1151491605000},"page":"202-213","source":"Crossref","is-referenced-by-count":0,"title":["Edge Disjoint Paths in Moderately Connected Graphs"],"prefix":"10.1007","author":[{"given":"Satish","family":"Rao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shuheng","family":"Zhou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"19_CR1","doi-asserted-by":"crossref","unstructured":"Andrews, M., Chuzhoy, J., Khanna, S., Zhang, L.: Hardness of the undirected edge-disjoint paths problem with congestion. In: Proceedings of the 46th IEEE FOCS (2005)","DOI":"10.1145\/1060590.1060632"},{"key":"19_CR2","doi-asserted-by":"crossref","unstructured":"Andrews, M., Zhang, L.: Hardness of the undirected congestion minimization problem. In: Proceedings of the 37th ACM STOC (2005)","DOI":"10.1145\/1060590.1060633"},{"key":"19_CR3","doi-asserted-by":"crossref","unstructured":"Andrews, M., Zhang, L.: Hardness of the undirected edge-disjoint path problem. In: Proceedings of the 37th ACM STOC (2005)","DOI":"10.1145\/1060590.1060632"},{"key":"19_CR4","doi-asserted-by":"crossref","unstructured":"Andrews, M., Zhang, L.: Logarithmic hardness of the directed congestion minimization problem. In: Proceedings of the 38th ACM STOC (2006)","DOI":"10.1145\/1132516.1132592"},{"key":"19_CR5","unstructured":"Aumann, Y., Rabani, Y.: Improved bounds for all-optical routing. In: Proceedings of the 6th ACM-SIAM SODA, pp. 567\u2013576 (1995)"},{"key":"19_CR6","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Gawlick, R., Leighton, F.T., Rabani, Y.: On-line admission control and circuit routing for high performance computing and communication. In: Proceedings of the 35th IEEE FOCS, pp. 412\u2013423 (1994)","DOI":"10.1109\/SFCS.1994.365675"},{"key":"19_CR7","doi-asserted-by":"publisher","first-page":"976","DOI":"10.1137\/S0097539792232021","volume":"23","author":"A. Broder","year":"1994","unstructured":"Broder, A., Frieze, A., Upfal, E.: Existence and construction of edge-disjoint paths on expander graphs. SIAM Journal of Computing\u00a023, 976\u2013989 (1994)","journal-title":"SIAM Journal of Computing"},{"key":"19_CR8","unstructured":"Chekuri, C., Khanna, S.: Edge disjoint paths revisited. In: Proceedings of the 14th ACM-SIAM SODA (2003)"},{"key":"19_CR9","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Khanna, S., Shepherd, F.B.: The all-or-nothing multicommodity flow problem. In: Proceedings of the 36th ACM STOC (2004)","DOI":"10.1145\/1007352.1007383"},{"key":"19_CR10","unstructured":"Chekuri, C., Khanna, S., Shepherd, F.B.: Edge-disjoint paths in planar graphs. In: Proceedings of the 45th IEEE FOCS (2004)"},{"key":"19_CR11","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Khanna, S., Shepherd, F.B.: Multicommodity flow, well-linked terminals, and routing problems. In: Proceedings of the 37th ACM STOC (2005)","DOI":"10.1145\/1060590.1060618"},{"key":"19_CR12","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Khanna, S., Shepherd, F.B.: Edge-disjoint paths in planar graphs with constant congestion. In: Proceedings of the 38th ACM STOC (2006)","DOI":"10.1145\/1132516.1132621"},{"key":"19_CR13","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 unsplittable flow. Journal of Theory of Computing\u00a02, 137\u2013146 (2006)","journal-title":"Journal of Theory of Computing"},{"key":"19_CR14","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., Naor, J.: New hardness results for congestion minimization and machine scheduling. In: Proceedings of the 36th ACM STOC, pp. 28\u201334 (2004)","DOI":"10.1145\/1007352.1007364"},{"key":"19_CR15","doi-asserted-by":"crossref","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. In: Proc. of the 20th ICALP (1993)","DOI":"10.1007\/3-540-56939-1_62"},{"key":"19_CR16","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1137\/S0097539793243016","volume":"25","author":"N. Garg","year":"1996","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Approximate max-flow min-(multi)cut theorems and their applications. SIAM J. of Computing\u00a025, 235\u2013251 (1996)","journal-title":"SIAM J. of Computing"},{"key":"19_CR17","doi-asserted-by":"crossref","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. In: Proceedings of the 31th ACM STOC (1999)","DOI":"10.1145\/301250.301262"},{"key":"19_CR18","doi-asserted-by":"crossref","unstructured":"Karger, D.R.: Random sampling in cut, flow, and network design problems. In: Proceedings of the 26th ACM STOC (1994)","DOI":"10.1145\/195058.195422"},{"key":"19_CR19","doi-asserted-by":"crossref","unstructured":"Khandekar, R., Rao, S., Vazirani, U.: Graph partitioning using single commodity flows. In: Proceedings of the 38th ACM STOC (2006)","DOI":"10.1145\/1132516.1132574"},{"key":"19_CR20","unstructured":"Kleinberg, J.: An approximation algorithm for the disjoint paths problem in even-degree planar graphs. In: Proceedings of the 46th IEEE FOCS (2005)"},{"key":"19_CR21","unstructured":"Kleinberg, J., Rubinfeld, R.: Short paths in expander graphs. In: Proceedings of the 37th IEEE FOCS (1996)"},{"key":"19_CR22","doi-asserted-by":"crossref","unstructured":"Kleinberg, J., Tardos, E.: Approximations for the disjoint paths problem in high-diameter planar networks. In: Proceedings of the 27th ACM STOC (1995)","DOI":"10.1145\/225058.225075"},{"key":"19_CR23","doi-asserted-by":"crossref","unstructured":"Kleinberg, J., Tardos, E.: Disjoint paths in densely embedded graphs. In: Proceedings of the 36th IEEE FOCS, pp. 52\u201361 (1995)","DOI":"10.1109\/SFCS.1995.492462"},{"key":"19_CR24","series-title":"PhD thesis","volume-title":"Approximation Algorithms for Disjoint Paths Problems","author":"J.M. Kleinberg","year":"1996","unstructured":"Kleinberg, J.M.: Approximation Algorithms for Disjoint Paths Problems. PhD thesis. MIT, Cambridge (1996)"},{"key":"19_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-69346-7_12","volume-title":"Integer Programming and Combinatorial Optimization","author":"S.G. Kolliopoulos","year":"1998","unstructured":"Kolliopoulos, S.G., Stein, C.: Approximating disjoint-path problems using greedy algorithms and packing integer programs. In: Bixby, R.E., Boyd, E.A., R\u00edos-Mercado, R.Z. (eds.) IPCO 1998. LNCS, vol.\u00a01412, Springer, Heidelberg (1998)"},{"key":"19_CR26","doi-asserted-by":"crossref","unstructured":"Kolman, P., Scheideler, C.: Simple on-line algorithms for the maximum disjoint paths problem. In: Proceedings of the 13th ACM SPAA (2001)","DOI":"10.1145\/378580.378586"},{"key":"19_CR27","doi-asserted-by":"crossref","unstructured":"Obata, K.: Approximate max-integral-flow\/min-multicut theorems. In: Proceedings of the 36th ACM STOC (2004)","DOI":"10.1145\/1007352.1007433"},{"key":"19_CR28","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/BF02579324","volume":"7","author":"P. Raghavan","year":"1987","unstructured":"Raghavan, P., Thompson, C.D.: Randomized roundings: a technique for provably good algorithms and algorithms proofs. Combinatorica\u00a07, 365\u2013374 (1987)","journal-title":"Combinatorica"},{"key":"19_CR29","first-page":"267","volume":"9","author":"N. Robertson","year":"1990","unstructured":"Robertson, N., Seymour, P.D.: An outline of a disjoint paths algorithm. Paths, Flows and VLSI-design, Algorithms and Combinatorics\u00a09, 267\u2013292 (1990)","journal-title":"Paths, Flows and VLSI-design, Algorithms and Combinatorics"},{"key":"19_CR30","unstructured":"Srinivasan, A.: Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems. In: Proceedings of the 38th IEEE FOCS (1997)"},{"key":"19_CR31","unstructured":"Varadarajan, K., Venkataraman, G.: Graph decomposition and a greedy algorithm for edge-disjoint paths. In: Proceedings of the ACM-SIAM SODA (2004)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11786986_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T16:15:22Z","timestamp":1736439322000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11786986_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540359043","9783540359050"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/11786986_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}