{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,21]],"date-time":"2025-04-21T13:05:59Z","timestamp":1745240759967,"version":"3.37.3"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,2,9]],"date-time":"2022-02-09T00:00:00Z","timestamp":1644364800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,2,9]],"date-time":"2022-02-09T00:00:00Z","timestamp":1644364800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"deutsche forschungsgemeinschaft","doi-asserted-by":"publisher","award":["CRC\/TRR 154, project A07"],"award-info":[{"award-number":["CRC\/TRR 154, project A07"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006188","name":"Einstein Stiftung Berlin","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100006188","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2023,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Potential-based flows provide a simple yet realistic mathematical model of transport in many real-world infrastructure networks such as, e.g., gas or water networks, where the flow along each edge depends on the difference of the potentials at its end nodes. We call a network topology robust if the maximal node potential needed to satisfy a set of demands never increases when demands are decreased. This notion of robustness is motivated by infrastructure networks where users first make reservations for certain demands that may be larger than the actual flows sent later on. In these networks, node potentials correspond to physical quantities such as pressures or hydraulic heads and must be guaranteed to lie within a fixed range, even if the actual amounts are smaller than the previously reserved demands. Our main results are a precise characterization of robust network topologies for the case of point-to-point demands via forbidden node-labeled graph minors, as well as an efficient algorithm for testing robustness.<\/jats:p>","DOI":"10.1007\/s10107-021-01760-w","type":"journal-article","created":{"date-parts":[[2022,2,9]],"date-time":"2022-02-09T16:02:46Z","timestamp":1644422566000},"page":"337-374","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On the robustness of potential-based flow networks"],"prefix":"10.1007","volume":"197","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9061-2267","authenticated-orcid":false,"given":"Max","family":"Klimm","sequence":"first","affiliation":[]},{"given":"Marc E.","family":"Pfetsch","sequence":"additional","affiliation":[]},{"given":"Rico","family":"Raber","sequence":"additional","affiliation":[]},{"given":"Martin","family":"Skutella","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,2,9]]},"reference":[{"key":"1760_CR1","doi-asserted-by":"publisher","first-page":"711","DOI":"10.1016\/j.ejor.2014.04.023","volume":"238","author":"E \u00c0lvarez-Miranda","year":"2014","unstructured":"\u00c0lvarez-Miranda, E., Cacchiani, V., Lodi, A., Parriani, T., Schmidt, D.R.: Single-commodity robust network design problem: complexity, instances and heuristic solutions. Eur. J. Oper. Res. 238, 711\u2013723 (2014). https:\/\/doi.org\/10.1016\/j.ejor.2014.04.023","journal-title":"Eur. J. Oper. Res."},{"key":"1760_CR2","volume-title":"Robust Optimization. Princeton Series in Applied Mathematics","author":"A Ben-Tal","year":"2009","unstructured":"Ben-Tal, A., Ghaoui, L.E., Nemirovski, A.S.: Robust Optimization. Princeton Series in Applied Mathematics. Princeton University Press, Princeton (2009)"},{"key":"1760_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0167-6377(99)00016-4","volume":"25","author":"A Ben-Tal","year":"1999","unstructured":"Ben-Tal, A., Nemirovski, A.: Robust solutions of uncertain linear programs. Oper. Res. Lett. 25, 1\u201313 (1999). https:\/\/doi.org\/10.1016\/S0167-6377(99)00016-4","journal-title":"Oper. Res. Lett."},{"key":"1760_CR4","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1287\/ijoc.8.3.243","volume":"8","author":"O Bienstock","year":"1996","unstructured":"Bienstock, O., G\u00fcnl\u00fck, O.: Capacitated network design\u2014polyhedral structure and computation. INFORMS J. Comput. 8, 243\u2013259 (1996). https:\/\/doi.org\/10.1287\/ijoc.8.3.243","journal-title":"INFORMS J. Comput."},{"issue":"4","key":"1760_CR5","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1090\/qam\/77398","volume":"13","author":"G Birkhoff","year":"1956","unstructured":"Birkhoff, G., Diaz, J.B.: Non-linear network problems. Q. Appl. Math. 13(4), 431\u2013443 (1956)","journal-title":"Q. Appl. Math."},{"key":"1760_CR6","doi-asserted-by":"publisher","unstructured":"Buchheim, C., Liers, F., Sanit\u00e0, L.: An exact algorithm for robust network design. In: Pahl, J., Reiners, T., Vo\u00df, S. (eds.) Network Optimization. INOC 2011, Lecture Notes in Computer Science, vol. 6701 (2011). https:\/\/doi.org\/10.1007\/978-3-642-21527-8_2","DOI":"10.1007\/978-3-642-21527-8_2"},{"key":"1760_CR7","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/s10107-016-0991-9","volume":"157","author":"V Cacchiani","year":"2016","unstructured":"Cacchiani, V., J\u00fcnger, M., Liers, F., Lodi, A., Schmidt, D.R.: Single-commodity robust network design with finite and Hose demand sets. Math. Progr. Ser. B 157, 297\u2013342 (2016). https:\/\/doi.org\/10.1007\/s10107-016-0991-9","journal-title":"Math. Progr. Ser. B"},{"issue":"3","key":"1760_CR8","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1147\/rd.43.0311","volume":"4","author":"RT Chien","year":"1960","unstructured":"Chien, R.T.: Synthesis of a communication net. IBM J. Res. Dev. 4(3), 311\u2013320 (1960). https:\/\/doi.org\/10.1147\/rd.43.0311","journal-title":"IBM J. Res. Dev."},{"key":"1760_CR9","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1109\/TCT.1970.1083100","volume":"17","author":"W Chou","year":"1970","unstructured":"Chou, W., Frank, H.: Survivable communication networks and the terminal capacity matrix. IEEE Trans. Circuit Theory 17, 192\u2013197 (1970). https:\/\/doi.org\/10.1109\/TCT.1970.1083100","journal-title":"IEEE Trans. Circuit Theory"},{"issue":"7","key":"1760_CR10","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1287\/mnsc.24.7.747","volume":"24","author":"M Collins","year":"1978","unstructured":"Collins, M., Cooper, L., Helgason, R., Kennington, J., LeBlanc, L.: Solving the pipe network analysis problem using optimization techniques. Manag. Sci. 24(7), 747\u2013760 (1978). https:\/\/doi.org\/10.1287\/mnsc.24.7.747","journal-title":"Manag. Sci."},{"issue":"11","key":"1760_CR11","doi-asserted-by":"publisher","first-page":"1454","DOI":"10.1287\/mnsc.46.11.1454.12087","volume":"46","author":"D De Wolf","year":"2000","unstructured":"De Wolf, D., Smeers, Y.: The gas transmission problem solved by an extension of the simplex algorithm. Manag. Sci. 46(11), 1454\u20131465 (2000)","journal-title":"Manag. Sci."},{"key":"1760_CR12","volume-title":"Graph Theory","author":"R Diestel","year":"2018","unstructured":"Diestel, R.: Graph Theory. Springer-Verlag, Berlin Heidelberg (2018)"},{"key":"1760_CR13","doi-asserted-by":"publisher","unstructured":"Duffield, N.G., Goyal, P., Greenberg, A., Mishra, P., Ramakrishnan, K.K., van\u00a0der Merwe, J.E.: A flexible model for resource management in virtual private networks. In: Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM), pp. 95\u2013108 (1999). https:\/\/doi.org\/10.1145\/316188.316209","DOI":"10.1145\/316188.316209"},{"issue":"2","key":"1760_CR14","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1006\/jagm.1997.0866","volume":"24","author":"JA Fingerhut","year":"1997","unstructured":"Fingerhut, J.A., Suri, S., Turner, J.S.: Designing least-cost nonblocking broadband networks. J. Algorithms 24(2), 287\u2013309 (1997). https:\/\/doi.org\/10.1006\/jagm.1997.0866","journal-title":"J. Algorithms"},{"key":"1760_CR15","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1287\/mnsc.5.1.97","volume":"5","author":"LR Ford Jr","year":"1958","unstructured":"Ford, L.R., Jr., Fulkerson, D.R.: A suggested computation for maximal multi-commodity network flows. Manag. Sci. 5, 97\u2013101 (1958)","journal-title":"Manag. Sci."},{"key":"1760_CR16","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1090\/conm\/065\/891251","volume":"65","author":"H Friedmann","year":"1987","unstructured":"Friedmann, H., Robertson, N., Seymour, P.D.: The metamathematics of the graph minor theorem. Contemp. Math. 65, 229\u2013261 (1987)","journal-title":"Contemp. Math."},{"key":"1760_CR17","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1137\/0109047","volume":"9","author":"RE Gomory","year":"1961","unstructured":"Gomory, R.E., Hu, T.C.: Multi-terminal network flows. J. Soc. Ind. Appl. Math. 9, 551\u2013570 (1961). https:\/\/doi.org\/10.1137\/0109047","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"1760_CR18","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1137\/0110020","volume":"10","author":"RE Gomory","year":"1962","unstructured":"Gomory, R.E., Hu, T.C.: An application of generalized linear programming to network flows. J. Soc. Ind. Appl. Math. 10, 260\u2013283 (1962)","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"1760_CR19","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1137\/0112029","volume":"12","author":"RE Gomory","year":"1964","unstructured":"Gomory, R.E., Hu, T.C.: Synthesis of a communication network. J. Soc. Ind. Appl. Math. 12, 348\u2013369 (1964). https:\/\/doi.org\/10.1137\/0112029","journal-title":"J. Soc. Ind. Appl. Math."},{"issue":"3","key":"1760_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2487241.2487243","volume":"60","author":"N Goyal","year":"2013","unstructured":"Goyal, N., Olver, N., Shepherd, B.: The VPN conjecture is true. J. ACM 60(3), 1\u201317 (2013). https:\/\/doi.org\/10.1145\/2487241.2487243","journal-title":"J. ACM"},{"key":"1760_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/s00186-018-0647-z","author":"V Grimm","year":"2018","unstructured":"Grimm, V., Schewe, L., Schmidt, M., Z\u00f6ttl, G.: A multilevel model of the European entry-exit gas market. Math. Methods Oper. Res. (2018). https:\/\/doi.org\/10.1007\/s00186-018-0647-z","journal-title":"Math. Methods Oper. Res."},{"key":"1760_CR22","doi-asserted-by":"publisher","DOI":"10.1002\/net.21865","author":"M Gro\u00df","year":"2018","unstructured":"Gro\u00df, M., Pfetsch, M.E., Schewe, L., Schmidt, M., Skutella, M.: Algorithmic results for potential-based flows: easy and hard cases. Networks (2018). https:\/\/doi.org\/10.1002\/net.21865","journal-title":"Networks"},{"key":"1760_CR23","doi-asserted-by":"publisher","unstructured":"Gupta, A., Kleinberg, J., Kumar, A., Rastogi, R., Yener, B.: Provisioning a virtual private network: a network design problem for multicommodity flow. In: Proceedings of the 33rd Annual ACM symposium on Theory of Computing (STOC), pp. 389\u2013398 (2001). https:\/\/doi.org\/10.1145\/380752.380830","DOI":"10.1145\/380752.380830"},{"key":"1760_CR24","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1137\/0212010","volume":"12","author":"D Gusfield","year":"1983","unstructured":"Gusfield, D.: Simple constructions for the multi-terminal network flow synthesis. SIAM J. Comput. 12, 157\u2013165 (1983). https:\/\/doi.org\/10.1137\/0212010","journal-title":"SIAM J. Comput."},{"issue":"4","key":"1760_CR25","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1080\/02630258408970343","volume":"1","author":"CT Hendrickson","year":"1984","unstructured":"Hendrickson, C.T., Janson, B.N.: A common network flow formulation for several civil engineering problems. Civ. Eng. Syst. 1(4), 195\u2013203 (1984). https:\/\/doi.org\/10.1080\/02630258408970343","journal-title":"Civ. Eng. Syst."},{"issue":"1","key":"1760_CR26","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1137\/050641776","volume":"23","author":"SN Kabadi","year":"2008","unstructured":"Kabadi, S.N., Yan, J., Du, D., Nair, K.P.K.: Integer exact network synthesis problem. SIAM J. Discrete Math. 23(1), 136\u2013154 (2008). https:\/\/doi.org\/10.1137\/050641776","journal-title":"SIAM J. Discrete Math."},{"key":"1760_CR27","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973693","volume-title":"Evaluating Gas Network Capacities","author":"T Koch","year":"2015","unstructured":"Koch, T., Hiller, B., Pfetsch, M.E., Schewe, L.: Evaluating Gas Network Capacities. Society for Industrial and Applied Mathematics, Philadelphia (2015)"},{"issue":"2","key":"1760_CR28","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1051\/ro\/1977110202431","volume":"11","author":"JJ Maugis","year":"1977","unstructured":"Maugis, J.J.: \u00c9tude de r\u00e9seaux de transport et de distribution de fluide. RAIRO Oper. Res. 11(2), 243\u2013248 (1977)","journal-title":"RAIRO Oper. Res."},{"key":"1760_CR29","doi-asserted-by":"publisher","unstructured":"Minoux, M.: Optimum synthesis of a network with non-simultaneous multicommodity flow requirements. In: Annals of Discrete Mathematics, Studies on Graphs and Discrete Programming, vol. 59, pp. 269\u2013277. North-Holland (1981). https:\/\/doi.org\/10.1016\/S0304-0208(08)73470-4","DOI":"10.1016\/S0304-0208(08)73470-4"},{"issue":"1","key":"1760_CR30","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XIII. The disjoint paths problem. J. Comb. Theory Ser. B 63(1), 65\u2013110 (1995). https:\/\/doi.org\/10.1006\/jctb.1995.1006","journal-title":"J. Comb. Theory Ser. B"},{"key":"1760_CR31","volume-title":"Network Flows and Monotropic Optimization","author":"RT Rockafellar","year":"1984","unstructured":"Rockafellar, R.T.: Network Flows and Monotropic Optimization. Wiley-Interscience, Hoboken (1984)"},{"key":"1760_CR32","unstructured":"Schmidt, D.R.: Robust design of single-commodity networks. Ph.D. thesis, K\u00f6ln University (2014)"},{"issue":"4","key":"1760_CR33","doi-asserted-by":"publisher","first-page":"40","DOI":"10.3390\/data2040040","volume":"2","author":"M Schmidt","year":"2017","unstructured":"Schmidt, M., A\u00dfmann, D., Burlacu, R., Humpola, J., Joormann, I., Kanelakis, N., Koch, T., Oucherif, D., Pfetsch, M.E., Schewe, L., Schwarz, R., Sirvent, M.: GasLib\u2014a library of gas network instances. Data 2(4), 40 (2017). https:\/\/doi.org\/10.3390\/data2040040","journal-title":"Data"},{"key":"1760_CR34","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1287\/moor.17.3.581","volume":"17","author":"R Sridhar","year":"1992","unstructured":"Sridhar, R., Chandrasekaran, R.: Integer solution to synthesis of communication networks. Math. Oper. Res. 17, 581\u2013585 (1992). https:\/\/doi.org\/10.1287\/moor.17.3.581","journal-title":"Math. Oper. Res."},{"key":"1760_CR35","unstructured":"Szab\u00f3, J.: The set of solutions to nomination validation in passive gas transportation networks with a generalized flow formula. Tech. Rep. 11\u201344, Zuse Institute Berlin (2012)"},{"key":"1760_CR36","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1002\/(SICI)1097-0037(199603)27:2<109::AID-NET2>3.0.CO;2-O","volume":"27","author":"KT Talluri","year":"1996","unstructured":"Talluri, K.T.: Network synthesis with few edges. Networks 27, 109\u2013115 (1996)","journal-title":"Networks"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01760-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-021-01760-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01760-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,22]],"date-time":"2023-01-22T01:06:43Z","timestamp":1674349603000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-021-01760-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,9]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["1760"],"URL":"https:\/\/doi.org\/10.1007\/s10107-021-01760-w","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2022,2,9]]},"assertion":[{"value":"29 March 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 November 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 February 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}