{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,17]],"date-time":"2025-09-17T07:15:10Z","timestamp":1758093310443,"version":"3.44.0"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,9,1]],"date-time":"2025-09-01T00:00:00Z","timestamp":1756684800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,9,1]],"date-time":"2025-09-01T00:00:00Z","timestamp":1756684800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100006360","name":"Bundesministerium f\u00fcr Wirtschaft und Energie","doi-asserted-by":"publisher","award":["FKZ 03ET4029"],"award-info":[{"award-number":["FKZ 03ET4029"]}],"id":[{"id":"10.13039\/501100006360","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005713","name":"Technische Universit\u00e4t M\u00fcnchen","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005713","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Optim Theory Appl"],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>In network flow problems, there is a well-known one-to-one relationship between extreme points of the feasibility region and trees in the associated undirected graph. The same is true for the dual differential problem. In this paper, we study a problem variant with both differential constraints and constraints on flow conservation at every node, which we call <jats:italic>differential flow<\/jats:italic>. This variant is motivated by an application in the expansion planning of energy networks. We show that all extreme points in the <jats:italic>differential flow polytope<\/jats:italic> still directly correspond to graph-theoretical structures in the underlying network, namely a generalization of spanning trees. The reverse is generally also true except in very special cases where the network parameters satisfy a set of particular equations. We furthermore show that these exceptional cases can never occur in cactus graphs and present additional, sufficient criteria for when the one-to-one correspondence between extreme points and graph-theoretical structures holds. Finally, we show that it is generally NP-hard to decide for a specific network whether the graph-theoretical characterization holds for all extreme points.<\/jats:p>","DOI":"10.1007\/s10957-025-02792-4","type":"journal-article","created":{"date-parts":[[2025,9,1]],"date-time":"2025-09-01T08:26:45Z","timestamp":1756715205000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Extremal Solutions for Network Flow with Differential Constraints"],"prefix":"10.1007","volume":"207","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2985-0549","authenticated-orcid":false,"given":"Ren\u00e9","family":"Brandenberg","sequence":"first","affiliation":[]},{"given":"Paul","family":"Stursberg","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,9,1]]},"reference":[{"key":"2792_CR1","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall (1993)"},{"key":"2792_CR2","first-page":"431","volume":"3","author":"J Carpentier","year":"1962","unstructured":"Carpentier, J.: Contribution L\u2019 tude du Dispatching conomique. Bull. Soc. Fr. Elec. Ser. 3, 431 (1962)","journal-title":"Bull. Soc. Fr. Elec. Ser."},{"key":"2792_CR3","first-page":"95","volume":"123","author":"SH Christie","year":"1833","unstructured":"Christie, S.H.: The Bakerian Lecture: Experimental determination of the laws of magneto-electric induction in different masses of the same metal, and of its intensity in different metals, and of Its Intensity in Different Metals. Philos. Trans. R. Soc. Lond. 123, 95\u2013142 (1833)","journal-title":"Philos. Trans. R. Soc. Lond."},{"key":"2792_CR4","doi-asserted-by":"crossref","unstructured":"Chung, F.R.: Spectral Graph Theory, CBMS Regional Conference Series in Mathematics, vol.\u00a092. American Mathematical Society (1997)","DOI":"10.1090\/cbms\/092"},{"key":"2792_CR5","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Theory, 5 edn. Graduate Texts in Mathematics. Springer (2017)","DOI":"10.1007\/978-3-662-53622-3"},{"issue":"2","key":"2792_CR6","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/0022-247X(65)90125-3","volume":"10","author":"RJ Duffin","year":"1965","unstructured":"Duffin, R.J.: Topology of series-parallel networks. J. Math. Anal. Appl. 10(2), 303\u2013318 (1965)","journal-title":"J. Math. Anal. Appl."},{"issue":"3","key":"2792_CR7","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1109\/31.1748","volume":"35","author":"ES El-Mallah","year":"1988","unstructured":"El-Mallah, E.S., Colbourn, C.J.: The Complexity of Some Edge Deletion Problems. IEEE Transactions on Circuits and Systems 35(3), 354\u2013362 (1988)","journal-title":"IEEE Transactions on Circuits and Systems"},{"key":"2792_CR8","volume-title":"Computers and Intractability","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. W. H, Freeman and Company (1979)"},{"issue":"3","key":"2792_CR9","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1002\/net.21865","volume":"73","author":"M Gro\u00df","year":"2019","unstructured":"Gro\u00df, M., Pfetsch, M.E., Schewe, L., Schmidt, M., Skutella, M.: Algorithmic results for Potential based flows: easy and hard cases. Networks 73(3), 306\u2013324 (2019)","journal-title":"Networks"},{"issue":"1","key":"2792_CR10","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/net.22038","volume":"79","author":"O Habeck","year":"2022","unstructured":"Habeck, O., Pfetsch, M.E.: Combinatorial acyclicity models for potential-based flows. Networks 79(1), 83\u2013104 (2022)","journal-title":"Networks"},{"key":"2792_CR11","doi-asserted-by":"crossref","unstructured":"Hewes, D., Altschaeffl, S., Boiarchuk, I., Witzmann, R.: Development of a dynamic model of the European transmission system using publicly available data. In: 2016 IEEE International Energy Conference (ENERGYCON), pp. 1\u20136. IEEE (2016)","DOI":"10.1109\/ENERGYCON.2016.7514144"},{"key":"2792_CR12","doi-asserted-by":"crossref","unstructured":"Leibfried, T., Mchedlidze, T., Meyer-H\u00fcbner, N., N\u00f6llenburg, M., Rutter, I., Sanders, P., Wagner, D., Wegner, F.: Operating power grids with few flow control buses. In: Proceedings of the 2015 ACM Sixth International Conference on Future Energy Systems, pp. 289\u2013294. ACM (2015)","DOI":"10.1145\/2768510.2768521"},{"key":"2792_CR13","unstructured":"Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Courier Corporation (1998)"},{"key":"2792_CR14","volume-title":"Network Flows and Monotropic Optimization","author":"RT Rockafellar","year":"1984","unstructured":"Rockafellar, R.T.: Network Flows and Monotropic Optimization. Wiley-Interscience, Pure and Applied Mathematics (1984)"},{"key":"2792_CR15","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/j.enpol.2011.12.040","volume":"43","author":"K Schaber","year":"2012","unstructured":"Schaber, K., Steinke, F., Hamacher, T.: Transmission grid extensions for the integration of variable renewable energies in Europe: Who benefits where? Energy Policy 43, 123\u2013135 (2012)","journal-title":"Energy Policy"},{"key":"2792_CR16","volume-title":"Combinatorial Optimization","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization. Springer, Algorithms and Combinatorics (2003)"},{"issue":"3","key":"2792_CR17","doi-asserted-by":"publisher","first-page":"1290","DOI":"10.1109\/TPWRS.2009.2021235","volume":"24","author":"B Stott","year":"2009","unstructured":"Stott, B., Jardim, J., Alsa\u00e7, O.: DC power flow revisited. IEEE Trans. Power Syst. 24(3), 1290\u20131300 (2009)","journal-title":"IEEE Trans. Power Syst."},{"key":"2792_CR18","unstructured":"Stursberg, P.: On the Mathematics of Energy System Optimization. Ph.D. thesis, Technical University of Munich (2019)"},{"issue":"2","key":"2792_CR19","doi-asserted-by":"publisher","first-page":"592","DOI":"10.1109\/TPWRS.2009.2016470","volume":"24","author":"A Tuohy","year":"2009","unstructured":"Tuohy, A., Meibom, P., Denny, E., O\u2019Malley, M.: Unit commitment for systems with significant wind penetration. IEEE Trans. Power Syst. 24(2), 592\u2013601 (2009)","journal-title":"IEEE Trans. Power Syst."},{"key":"2792_CR20","first-page":"303","volume":"133","author":"C Wheatstone","year":"1843","unstructured":"Wheatstone, C.: The Bakerian Lecture: An account of several new instruments and processes for determining the constants of a voltaic circuit. Philos. Trans. R. Soc. Lond. 133, 303\u2013327 (1843)","journal-title":"Philos. Trans. R. Soc. Lond."},{"issue":"2","key":"2792_CR21","doi-asserted-by":"publisher","first-page":"788","DOI":"10.1109\/TPWRS.2012.2208205","volume":"28","author":"B Zhang","year":"2013","unstructured":"Zhang, B., Tse, D.: Geometry of injection regions of power networks. IEEE Trans. Power Syst. 28(2), 788\u2013797 (2013)","journal-title":"IEEE Trans. Power Syst."},{"key":"2792_CR22","doi-asserted-by":"crossref","unstructured":"Zhu, J.: Optimization of Power System Operation. John Wiley & Sons (2015)","DOI":"10.1002\/9781118887004"}],"container-title":["Journal of Optimization Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-025-02792-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10957-025-02792-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-025-02792-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,16]],"date-time":"2025-09-16T07:44:36Z","timestamp":1758008676000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10957-025-02792-4"}},"subtitle":["A Generalization of Spanning Trees"],"short-title":[],"issued":{"date-parts":[[2025,9,1]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["2792"],"URL":"https:\/\/doi.org\/10.1007\/s10957-025-02792-4","relation":{},"ISSN":["0022-3239","1573-2878"],"issn-type":[{"type":"print","value":"0022-3239"},{"type":"electronic","value":"1573-2878"}],"subject":[],"published":{"date-parts":[[2025,9,1]]},"assertion":[{"value":"23 October 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 July 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 September 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"70"}}