{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:41:30Z","timestamp":1767339690855},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2014,12,21]],"date-time":"2014-12-21T00:00:00Z","timestamp":1419120000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2015,12]]},"DOI":"10.1007\/s10107-014-0856-z","type":"journal-article","created":{"date-parts":[[2014,12,19]],"date-time":"2014-12-19T20:20:57Z","timestamp":1419020457000},"page":"249-272","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["The all-or-nothing flow problem in directed graphs with symmetric demand pairs"],"prefix":"10.1007","volume":"154","author":[{"given":"Chandra","family":"Chekuri","sequence":"first","affiliation":[]},{"given":"Alina","family":"Ene","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,12,21]]},"reference":[{"issue":"5","key":"856_CR1","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1016\/j.jctb.2006.12.006","volume":"97","author":"I Adler","year":"2007","unstructured":"Adler, I.: Directed tree-width examples. J Comb. Theory Ser. B 97(5), 718\u2013725 (2007)","journal-title":"J Comb. Theory Ser. B"},{"issue":"5","key":"856_CR2","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1007\/s00493-010-2455-9","volume":"30","author":"M Andrews","year":"2010","unstructured":"Andrews, M., Chuzhoy, J., Guruswami, V., Khanna, S., Talwar, K., Zhang, L.: Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs. Combinatorica 30(5), 485\u2013520 (2010)","journal-title":"Combinatorica"},{"key":"856_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: Proceeding of IEEE FOCS, pp. 226\u2013241 (2005)","DOI":"10.1109\/SFCS.2005.41"},{"key":"856_CR4","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Chuzhoy, J.: Large-treewidth graph decompositions and applications. In: Proceedings of ACM STOC (2013)","DOI":"10.1145\/2488608.2488645"},{"key":"856_CR5","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Chuzhoy, J.: Polynomial bounds for the grid-minor theorem. In: Proceedings of ACM STOC (2014)","DOI":"10.1145\/2591796.2591813"},{"key":"856_CR6","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Ene, A.: Poly-logarithmic approximation for maximum node disjoint paths with constant congestion. In: Proceedings of ACM-SIAM SODA (2013)","DOI":"10.1137\/1.9781611973105.24"},{"key":"856_CR7","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Kannan, S., Raja, A., Viswanath, P.: Multicommodity flows and cuts in polymatroidal networks. In: Proceedings of ITCS, pp. 399\u2013408 (2012)","DOI":"10.1145\/2090236.2090268"},{"issue":"4","key":"856_CR8","doi-asserted-by":"crossref","first-page":"1467","DOI":"10.1137\/100796820","volume":"42","author":"C Chekuri","year":"2013","unstructured":"Chekuri, C., Khanna, S., Shepherd, F.B.: The all-or-nothing multicommodity flow problem. SIAM J. Comput. 42(4), 1467\u20131493 (2013)","journal-title":"SIAM J. Comput."},{"key":"856_CR9","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Khanna, S., Shepherd, F.B.: Multicommodity flow, well-linked terminals, and routing problems. In: Proceedings of ACM STOC, pp. 183\u2013192 (2005)","DOI":"10.1145\/1060590.1060618"},{"key":"856_CR10","unstructured":"Chekuri, C., Khanna, S., Shepherd, F.B.: Well-linked terminals for node-capacitated routing problems. Manuscript (2005)"},{"issue":"7","key":"856_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})$$ O ( n ) approximation and integrality gap for disjoint paths and unsplittable flow. Theory Comput. 2(7), 137\u2013146 (2006)","journal-title":"Theory Comput."},{"issue":"3","key":"856_CR12","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1145\/1273340.1273343","volume":"3","author":"C Chekuri","year":"2007","unstructured":"Chekuri, C., Mydlarz, M., Shepherd, F.B.: Multicommodity demand flow in a tree and packing integer programs. ACM Trans. Algorithms 3(3), 27 (2007)","journal-title":"ACM Trans. Algorithms"},{"key":"856_CR13","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J.: Routing in undirected graphs with constant congestion. ArXiv preprint arXiv:1107.2554 (2011). Extended abstract in STOC 2012","DOI":"10.1145\/2213977.2214054"},{"key":"856_CR14","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., Guruswami, V., Khanna, S., Talwar, K.: Hardness of routing with congestion in directed graphs. In: Proceedings of ACM STOC, pp. 165\u2013178 (2007)","DOI":"10.1145\/1250790.1250816"},{"issue":"2","key":"856_CR15","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1145\/1502793.1502795","volume":"56","author":"J Chuzhoy","year":"2009","unstructured":"Chuzhoy, J., Khanna, S.: Polynomial flow-cut gaps and hardness of directed cut problems. J. ACM 56(2), 6 (2009)","journal-title":"J. ACM"},{"key":"856_CR16","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., Li, S.: A polylogarithimic approximation algorithm for edge-disjoint paths with congestion 2. In: Proceedings of IEEE FOCS (2012)","DOI":"10.1109\/FOCS.2012.54"},{"issue":"4","key":"856_CR17","doi-asserted-by":"crossref","first-page":"691","DOI":"10.1137\/0205048","volume":"5","author":"S Even","year":"1976","unstructured":"Even, S., Itai, A., Shamir, A.: On the complexity of timetable and multicommodity flow problems. SIAM J. Comput. 5(4), 691\u2013703 (1976)","journal-title":"SIAM J. Comput."},{"key":"856_CR18","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1137\/05064299X","volume":"38","author":"U Feige","year":"2008","unstructured":"Feige, U., Hajiaghayi, M.T., Lee, J.R.: Improved approximation algorithms for minimum weight vertex separators. SIAM J. Comput. 38, 629\u2013657 (2008)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"856_CR19","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S Fortune","year":"1980","unstructured":"Fortune, S., Hopcroft, J., Wyllie, J.: The directed subgraph homeomorphism problem. Theor. Comput. Sci. 10(2), 111\u2013121 (1980)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"856_CR20","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF02523685","volume":"18","author":"N Garg","year":"1997","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18(1), 3\u201320 (1997)","journal-title":"Algorithmica"},{"issue":"1","key":"856_CR21","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1006\/jctb.2000.2031","volume":"82","author":"T Johnson","year":"2001","unstructured":"Johnson, T., Robertson, N., Seymour, P.D., Thomas, R.: Directed tree-width. J. Comb. Theory Ser. B 82(1), 138\u2013154 (2001)","journal-title":"J. Comb. Theory Ser. B"},{"key":"856_CR22","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85\u2013103. Plenum press, New York (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"856_CR23","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Kreutzer, S.: An excluded grid theorem for digraphs with forbidden minors. In: Proceedings of ACM-SIAM SODA (2014)","DOI":"10.1137\/1.9781611973402.6"},{"key":"856_CR24","doi-asserted-by":"crossref","unstructured":"Kobayashi, Y., Kawarabayashi, K-I, Kreutzer, S.: An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem. In: Proceedings of ACM STOC (2014)","DOI":"10.1145\/2591796.2591876"},{"key":"856_CR25","doi-asserted-by":"crossref","unstructured":"Klein, P.N., Plotkin, S.A., Rao, S.: Excluded minors, network decomposition, and multicommodity flow. In: Proceedings of ACM STOC, pp. 682\u2013690 (1993)","DOI":"10.1145\/167088.167261"},{"issue":"2","key":"856_CR26","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1006\/jagm.1996.0833","volume":"22","author":"PN Klein","year":"1997","unstructured":"Klein, P.N., Plotkin, S.A., Rao, S., Tardos, E.: Approximation algorithms for Steiner and directed multicuts. J. Algorithms 22(2), 241\u2013269 (1997)","journal-title":"J. Algorithms"},{"issue":"6","key":"856_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. J. ACM 46(6), 787\u2013832 (1999)","journal-title":"J. ACM"},{"issue":"2","key":"856_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)","journal-title":"Combinatorica"},{"key":"856_CR29","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1016\/S1571-0653(05)80061-7","volume":"3","author":"B Reed","year":"1999","unstructured":"Reed, B.: Introducing directed tree width. Electr. Notes Discr. Math. 3, 222\u2013229 (1999)","journal-title":"Electr. Notes Discr. Math."},{"issue":"3","key":"856_CR30","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1007\/s00493-004-0031-x","volume":"24","author":"Michael E Saks","year":"2004","unstructured":"Saks, Michael E., Samorodnitsky, Alex, Zosin, Leonid: A lower bound on the integrality gap for minimum multicut in directed networks. Combinatorica 24(3), 525\u2013530 (2004)","journal-title":"Combinatorica"},{"key":"856_CR31","doi-asserted-by":"crossref","unstructured":"Srinivasan, A.: Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems. In: Proceedings of IEEE FOCS, pp. 416\u2013425 (1997)","DOI":"10.1109\/SFCS.1997.646130"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-014-0856-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-014-0856-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-014-0856-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,18]],"date-time":"2019-08-18T12:48:48Z","timestamp":1566132528000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-014-0856-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,21]]},"references-count":31,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2015,12]]}},"alternative-id":["856"],"URL":"https:\/\/doi.org\/10.1007\/s10107-014-0856-z","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12,21]]}}}