{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T13:28:23Z","timestamp":1760016503841,"version":"3.40.3"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031327254"},{"type":"electronic","value":"9783031327261"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-32726-1_29","type":"book-chapter","created":{"date-parts":[[2023,5,21]],"date-time":"2023-05-21T20:28:43Z","timestamp":1684700923000},"page":"408-422","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Cut-Sufficient Directed 2-Commodity Multiflow Topologies"],"prefix":"10.1007","author":[{"given":"Joseph","family":"Poremba","sequence":"first","affiliation":[]},{"given":"F. Bruce","family":"Shepherd","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,5,22]]},"reference":[{"key":"29_CR1","doi-asserted-by":"publisher","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, https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0095895606001444","DOI":"10.1016\/j.jctb.2006.12.006"},{"key":"29_CR2","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, California, USA (2007). https:\/\/doi.org\/10.1145\/1250790.1250888, http:\/\/portal.acm.org\/citation.cfm?doid=1250790.1250888","DOI":"10.1145\/1250790.1250888"},{"issue":"1","key":"29_CR3","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)","journal-title":"SIAM J. Comput."},{"key":"29_CR4","doi-asserted-by":"crossref","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)","DOI":"10.1145\/2213977.2213980"},{"key":"29_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, PA, USA, October 2008. https:\/\/doi.org\/10.1109\/FOCS.2008.79, http:\/\/ieeexplore.ieee.org\/document\/4691008\/","DOI":"10.1109\/FOCS.2008.79"},{"key":"29_CR6","doi-asserted-by":"publisher","unstructured":"Chekuri, C., Gupta, A., Newman, I., Rabinovich, Y., Sinclair, A.: Embedding k-outerplanar graphs into l1. SIAM J. Discret. Math. 20(1), 119\u2013136 (2006). https:\/\/doi.org\/10.1137\/S0895480102417379, http:\/\/epubs.siam.org\/doi\/10.1137\/S0895480102417379","DOI":"10.1137\/S0895480102417379"},{"issue":"2","key":"29_CR7","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)","journal-title":"J. Comb. Theory Ser. B"},{"key":"29_CR8","unstructured":"Deligkas, A., Meir, R.: Directed graph minors and serial-parallel width. In: 43rd International Symposium on Mathematical Foundations of Computer Science, vol. 21, p. 38 (2018)"},{"key":"29_CR9","doi-asserted-by":"publisher","unstructured":"Fortune, S., Hopcroft, J., Wyllie, J.: The directed subgraph homeomorphism problem. Theor. Comput. Sci. 10(2), 111\u2013121 (1980). https:\/\/doi.org\/10.1016\/0304-3975(80)90009-2, http:\/\/www.sciencedirect.com\/science\/article\/pii\/0304397580900092","DOI":"10.1016\/0304-3975(80)90009-2"},{"issue":"2","key":"29_CR10","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/s00493-004-0015-x","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)","journal-title":"Combinatorica"},{"key":"29_CR11","doi-asserted-by":"publisher","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, https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0020019005002929","DOI":"10.1016\/j.ipl.2005.10.005"},{"key":"29_CR12","doi-asserted-by":"publisher","unstructured":"Hu, T.C.: Multi-commodity network flows. Oper. Res. 11(3), 344\u2013360 (1963). https:\/\/doi.org\/10.1287\/opre.11.3.344, http:\/\/pubsonline.informs.org\/doi\/10.1287\/opre.11.3.344","DOI":"10.1287\/opre.11.3.344"},{"key":"29_CR13","doi-asserted-by":"publisher","unstructured":"Johnson, T., Robertson, N., Seymour, P., Thomas, R.: Directed tree-width. J. Comb. Theory Ser. B 82(1), 138\u2013154 (2001). https:\/\/doi.org\/10.1006\/jctb.2000.2031, https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0095895600920318","DOI":"10.1006\/jctb.2000.2031"},{"key":"29_CR14","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 Oregon USA, June 2015. https:\/\/doi.org\/10.1145\/2746539.2746586, https:\/\/dl.acm.org\/doi\/10.1145\/2746539.2746586","DOI":"10.1145\/2746539.2746586"},{"key":"29_CR15","doi-asserted-by":"publisher","unstructured":"Kawarabayashi, K.I., Sidiropoulos, A.: Embeddings of planar quasimetrics into directed $$\\ell $$$$_{\\rm 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, CO, USA, February 2022. https:\/\/doi.org\/10.1109\/FOCS52979.2021.00055, https:\/\/ieeexplore.ieee.org\/document\/9719783\/","DOI":"10.1109\/FOCS52979.2021.00055"},{"key":"29_CR16","doi-asserted-by":"publisher","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, https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0095895614001403","DOI":"10.1016\/j.jctb.2014.12.005"},{"key":"29_CR17","doi-asserted-by":"publisher","unstructured":"Kintali, S., Zhang, Q.: Forbidden directed minors and Kelly-width. Theor. Comput. Sci. 662, 40\u201347 (2017). https:\/\/doi.org\/10.1016\/j.tcs.2016.12.008, https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397516307149","DOI":"10.1016\/j.tcs.2016.12.008"},{"key":"29_CR18","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. Society for Industrial and Applied Mathematics, January 2012. https:\/\/doi.org\/10.1137\/1.9781611973099.123, https:\/\/epubs.siam.org\/doi\/10.1137\/1.9781611973099.123","DOI":"10.1137\/1.9781611973099.123"},{"key":"29_CR19","doi-asserted-by":"publisher","unstructured":"Lee, J.R., Raghavendra, P.: Coarse differentiation and multi-flows in planar graphs. Discret. Comput. Geom. 43(2), 346\u2013362 (2010). https:\/\/doi.org\/10.1007\/s00454-009-9172-4, http:\/\/link.springer.com\/10.1007\/s00454-009-9172-4","DOI":"10.1007\/s00454-009-9172-4"},{"key":"29_CR20","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 Theory of Computing - STOC \u201909, p. 245. ACM Press, Bethesda, MD, USA (2009). https:\/\/doi.org\/10.1145\/1536414.1536450, http:\/\/portal.acm.org\/citation.cfm?doid=1536414.1536450","DOI":"10.1145\/1536414.1536450"},{"issue":"6","key":"29_CR21","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)","journal-title":"J. ACM"},{"issue":"2","key":"29_CR22","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)","journal-title":"Combinatorica"},{"key":"29_CR23","unstructured":"Lomonosov, M.V.: Combinatorial approaches to multiflow problems. North-Holland (1985)"},{"key":"29_CR24","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)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"29_CR25","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. Discret. Math. 36(3), 1567\u20131585 (2022)","journal-title":"SIAM J. Discret. Math."},{"key":"29_CR26","doi-asserted-by":"crossref","unstructured":"Okamura, H., Seymour, P.D.: Multicommodity flows in planar graphs. J. Comb. Theory Ser. B 31(1), 75\u201381 (1981). http:\/\/www.sciencedirect.com\/science\/article\/B6WHT-4KBW025-8\/2\/9b4489ece0a97e9d8340d69948600501","DOI":"10.1016\/S0095-8956(81)80012-3"},{"key":"29_CR27","unstructured":"Poremba, J.C.: Directed multicommodity flows: cut-sufficiency and forbidden relevant minors. Master\u2019s thesis, University of British Columbia (2022)"},{"key":"29_CR28","doi-asserted-by":"crossref","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)","DOI":"10.1137\/1.9781611975482.34"},{"key":"29_CR29","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, vol. 24. Springer, Heidelberg (2003)"},{"issue":"1","key":"29_CR30","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)","journal-title":"Networks"},{"issue":"3","key":"29_CR31","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)","journal-title":"Eur. J. Comb."}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-32726-1_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,21]],"date-time":"2023-05-21T20:31:31Z","timestamp":1684701091000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-32726-1_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031327254","9783031327261"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-32726-1_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"22 May 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IPCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integer Programming and Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Madison, WI","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 June 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 June 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/optimization.discovery.wisc.edu\/ipco-2023-madison\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"119","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"33","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"28% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}