{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T05:39:55Z","timestamp":1740807595913,"version":"3.38.0"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2025,2,3]],"date-time":"2025-02-03T00:00:00Z","timestamp":1738540800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,2,3]],"date-time":"2025-02-03T00:00:00Z","timestamp":1738540800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2025,3]]},"DOI":"10.1007\/s10107-025-02195-3","type":"journal-article","created":{"date-parts":[[2025,2,3]],"date-time":"2025-02-03T07:08:47Z","timestamp":1738566527000},"page":"793-814","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Cut-sufficient directed 2-commodity multiflow topologies"],"prefix":"10.1007","volume":"210","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3210-5504","authenticated-orcid":false,"given":"Joseph","family":"Poremba","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"F. Bruce","family":"Shepherd","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,2,3]]},"reference":[{"issue":"6","key":"2195_CR1","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1145\/331524.331526","journal-title":"J. ACM"},{"issue":"1","key":"2195_CR2","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1137\/S0097539794285983","volume":"27","author":"Y Aumann","year":"1998","unstructured":"Aumann, Y., Rabani, Y.: An $$O (\\log k)$$ approximate min-cut max-flow theorem and approximation algorithm. SIAM J. Comput. 27(1), 291\u2013301 (1998). https:\/\/doi.org\/10.1137\/S0097539794285983","journal-title":"SIAM J. Comput."},{"issue":"2","key":"2195_CR3","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1007\/BF01200757","journal-title":"Combinatorica"},{"issue":"2","key":"2195_CR4","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1016\/j.jctb.2012.11.002","volume":"103","author":"C Chekuri","year":"2013","unstructured":"Chekuri, C., Shepherd, F.B., Weibel, C.: Flow-cut gaps for integer and fractional multiflows. J. Comb. Theory Ser. B 103(2), 248\u2013273 (2013). https:\/\/doi.org\/10.1016\/j.jctb.2012.11.002","journal-title":"J. Comb. Theory Ser. B"},{"key":"2195_CR5","doi-asserted-by":"publisher","unstructured":"Chakrabarti, A., Jaffe, A., Lee, J.R., Vincent, J.: Embeddings of topological graphs: lossy invariants, linearization, and 2-sums. In: 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 761\u2013770. IEEE, Philadelphia (2008). https:\/\/doi.org\/10.1109\/FOCS.2008.79. http:\/\/ieeexplore.ieee.org\/document\/4691008\/","DOI":"10.1109\/FOCS.2008.79"},{"issue":"1","key":"2195_CR6","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1137\/S0895480102417379","volume":"20","author":"C Chekuri","year":"2006","unstructured":"Chekuri, C., Gupta, A., Newman, I., Rabinovich, Y., Sinclair, A.: Embedding k-outerplanar graphs into l1. SIAM J. Discrete Math. 20(1), 119\u2013136 (2006). https:\/\/doi.org\/10.1137\/S0895480102417379","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"2195_CR7","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1109\/SFFCS.1999.814611","volume":"24","author":"A Gupta","year":"2004","unstructured":"Gupta, A., Newman, I., Rabinovich, Y., Sinclair, A.: Cuts, trees and $$\\ell _1$$-embeddings of graphs. Combinatorica 24(2), 233\u2013269 (2004). https:\/\/doi.org\/10.1109\/SFFCS.1999.814611","journal-title":"Combinatorica"},{"issue":"2","key":"2195_CR8","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1007\/s00454-009-9172-4","volume":"43","author":"JR Lee","year":"2010","unstructured":"Lee, J.R., Raghavendra, P.: Coarse differentiation and multi-flows in planar graphs. Discrete Comput. Geom. 43(2), 346\u2013362 (2010). https:\/\/doi.org\/10.1007\/s00454-009-9172-4","journal-title":"Discrete Comput. Geom."},{"key":"2195_CR9","doi-asserted-by":"publisher","unstructured":"Lee, J.R., Sidiropoulos, A.: On the geometry of graphs with a forbidden minor. In: Proceedings of the 41st Annual ACM Symposium on Symposium on Theory of Computing-STOC \u201909, p. 245. ACM Press, Bethesda (2009). https:\/\/doi.org\/10.1145\/1536414.1536450. http:\/\/portal.acm.org\/citation.cfm?doid=1536414.1536450","DOI":"10.1145\/1536414.1536450"},{"issue":"3","key":"2195_CR10","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1287\/opre.11.3.344","volume":"11","author":"TC Hu","year":"1963","unstructured":"Hu, T.C.: Multi-commodity network flows. Oper. Res. 11(3), 344\u2013360 (1963). https:\/\/doi.org\/10.1287\/opre.11.3.344","journal-title":"Oper. Res."},{"key":"2195_CR11","doi-asserted-by":"publisher","unstructured":"Okamura, H., Seymour, P.D.: Multicommodity flows in planar graphs. J. Comb. Theory Ser. B 31(1), 75\u201381 (1981\/8). https:\/\/doi.org\/10.1016\/S0095-8956(81)80012-3","DOI":"10.1016\/S0095-8956(81)80012-3"},{"key":"2195_CR12","doi-asserted-by":"publisher","unstructured":"Chakrabarti, A., Fleischer, L., Weibel, C.: When the cut condition is enough: a complete characterization for multiflow problems in series-parallel networks. In: Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, pp. 19\u201326. ACM (2012). https:\/\/doi.org\/10.1145\/2213977.2213980","DOI":"10.1145\/2213977.2213980"},{"key":"2195_CR13","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/0020-0190(89)90087-2","volume":"31","author":"H Nagamochi","year":"1989","unstructured":"Nagamochi, H., Ibaraki, T.: On max-flow min-cut and integral flow properties for multicommodity flows in directed graphs. Inf. Process. Lett. 31, 279\u2013285 (1989). https:\/\/doi.org\/10.1016\/0020-0190(89)90087-2","journal-title":"Inf. Process. Lett."},{"key":"2195_CR14","unstructured":"Lomonosov, M.V.: Combinatorial approaches to multiflow problems. Discrete Appl. Math. (1985)"},{"issue":"1","key":"2195_CR15","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1002\/net.3230100108","volume":"10","author":"PD Seymour","year":"1980","unstructured":"Seymour, P.D.: Four-terminus flows. Networks 10(1), 79\u201386 (1980). https:\/\/doi.org\/10.1002\/net.3230100108","journal-title":"Networks"},{"key":"2195_CR16","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics. Springer, Berlin (2003)"},{"issue":"3","key":"2195_CR17","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/S0195-6698(81)80033-9","volume":"2","author":"PD Seymour","year":"1981","unstructured":"Seymour, P.D.: Matroids and multicommodity flows. Eur. J. Comb. 2(3), 257\u2013290 (1981). https:\/\/doi.org\/10.1016\/S0195-6698(81)80033-9","journal-title":"Eur. J. Comb."},{"issue":"3","key":"2195_CR18","doi-asserted-by":"publisher","first-page":"1567","DOI":"10.1137\/20M1356968","volume":"36","author":"G Naves","year":"2022","unstructured":"Naves, G., Shepherd, B.: When do gomory-hu subtrees exist? SIAM J. Discrete Math. 36(3), 1567\u20131585 (2022). https:\/\/doi.org\/10.1137\/20M1356968","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"2195_CR19","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1006\/jctb.2000.2031","journal-title":"J. Comb. Theory Ser. B"},{"issue":"5","key":"2195_CR20","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1016\/j.jctb.2006.12.006","journal-title":"J. Comb. Theory Ser. B"},{"key":"2195_CR21","doi-asserted-by":"publisher","unstructured":"Kawarabayashi, K.-I., Kreutzer, S.: The directed grid theorem. In: Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, pp. 655\u2013664. ACM, Portland (2015). https:\/\/doi.org\/10.1145\/2746539.2746586","DOI":"10.1145\/2746539.2746586"},{"key":"2195_CR22","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.tcs.2016.12.008","volume":"662","author":"S Kintali","year":"2017","unstructured":"Kintali, S., Zhang, Q.: Forbidden directed minors and Kelly-width. Theoret. Comput. Sci. 662, 40\u201347 (2017). https:\/\/doi.org\/10.1016\/j.tcs.2016.12.008","journal-title":"Theoret. Comput. Sci."},{"key":"2195_CR23","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1016\/j.jctb.2014.12.005","volume":"112","author":"I Kim","year":"2015","unstructured":"Kim, I., Seymour, P.: Tournament minors. J. Comb. Theory Ser. B 112, 138\u2013153 (2015). https:\/\/doi.org\/10.1016\/j.jctb.2014.12.005","journal-title":"J. Comb. Theory Ser. B"},{"key":"2195_CR24","doi-asserted-by":"publisher","unstructured":"Deligkas, A., Meir, R.: Directed graph minors and serial-parallel width. In: Potapov, I., Spirakis, P., Worrell, J. (eds.) 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), vol. 117, pp. 44\u201314414. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2018). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2018.44. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2018\/9626","DOI":"10.4230\/LIPIcs.MFCS.2018.44"},{"key":"2195_CR25","doi-asserted-by":"publisher","unstructured":"Kreutzer, S., Tazari, S.: Directed nowhere dense classes of graphs. In: Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1552\u20131562. SIAM (2012). https:\/\/doi.org\/10.1137\/1.9781611973099.123","DOI":"10.1137\/1.9781611973099.123"},{"issue":"4","key":"2195_CR26","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1016\/j.ipl.2005.10.005","volume":"97","author":"MT Hajiaghayi","year":"2006","unstructured":"Hajiaghayi, M.T., R\u00e4cke, H.: An $$O(\\sqrt{n})$$-approximation algorithm for directed sparsest cut. Inf. Process. Lett. 97(4), 156\u2013160 (2006). https:\/\/doi.org\/10.1016\/j.ipl.2005.10.005","journal-title":"Inf. Process. Lett."},{"key":"2195_CR27","doi-asserted-by":"publisher","unstructured":"Agarwal, A., Alon, N., Charikar, M.S.: Improved approximation for directed cut problems. In: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing-STOC \u201907, p. 671. ACM Press, San Diego (2007). https:\/\/doi.org\/10.1145\/1250790.1250888. http:\/\/portal.acm.org\/citation.cfm?doid=1250790.1250888","DOI":"10.1145\/1250790.1250888"},{"key":"2195_CR28","doi-asserted-by":"publisher","unstructured":"Salmasi, A., Sidiropoulos, A., Sridhar, V.: On constant multi-commodity flow-cut gaps for families of directed minor-free graphs. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 535\u2013553. SIAM (2019). https:\/\/doi.org\/10.1137\/1.9781611975482.34","DOI":"10.1137\/1.9781611975482.34"},{"key":"2195_CR29","doi-asserted-by":"publisher","unstructured":"Kawarabayashi, K.-I., Sidiropoulos, A.: Embeddings of planar quasimetrics into directed $$\\ell _{{1}}$$ and polylogarithmic approximation for directed sparsest-cut. In: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 480\u2013491. IEEE, Denver (2022). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00055. https:\/\/ieeexplore.ieee.org\/document\/9719783\/","DOI":"10.1109\/FOCS52979.2021.00055"},{"issue":"2","key":"2195_CR30","doi-asserted-by":"publisher","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. Theoret. Comput. Sci. 10(2), 111\u2013121 (1980). https:\/\/doi.org\/10.1016\/0304-3975(80)90009-2","journal-title":"Theoret. Comput. Sci."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-025-02195-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-025-02195-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-025-02195-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,28]],"date-time":"2025-02-28T16:05:26Z","timestamp":1740758726000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-025-02195-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,3]]},"references-count":30,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["2195"],"URL":"https:\/\/doi.org\/10.1007\/s10107-025-02195-3","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2025,2,3]]},"assertion":[{"value":"31 July 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 January 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 February 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"None.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}