{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T00:06:41Z","timestamp":1767139601257,"version":"build-2238731810"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,1,28]],"date-time":"2025-01-28T00:00:00Z","timestamp":1738022400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,1,28]],"date-time":"2025-01-28T00:00:00Z","timestamp":1738022400000},"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":["CH 897\/7-1"],"award-info":[{"award-number":["CH 897\/7-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["CH 897\/7-1"],"award-info":[{"award-number":["CH 897\/7-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["461207633"],"award-info":[{"award-number":["461207633"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2025,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We introduce and discuss the  problem: given a directed graph with edge capacities\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\textit{cap} $$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>cap<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    and a retention ratio\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\alpha \\in (0,1)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>\u03b1<\/mml:mi>\n                            <mml:mo>\u2208<\/mml:mo>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mn>0<\/mml:mn>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , find the smallest subgraph that, for each pair of vertices\u00a0(\n                    <jats:italic>u<\/jats:italic>\n                    ,\u00a0\n                    <jats:italic>v<\/jats:italic>\n                    ), preserves at least a fraction\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\alpha $$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>\u03b1<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    of a maximum\n                    <jats:italic>u<\/jats:italic>\n                    -\n                    <jats:italic>v<\/jats:italic>\n                    -flow\u2019s value. This problem originates from the practical setting of reducing the power consumption in a computer network: it models turning off as many links as possible, while retaining the ability to transmit at least\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\alpha $$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>\u03b1<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    times the traffic compared to the original network. First we prove that  is NP-hard already on a restricted set of directed acyclic graphs (DAGs) with unit edge capacities. Our reduction also shows that a closely related problem (which only considers the arguably most complicated core of the problem in the objective function) is NP-hard to approximate within a sublogarithmic factor already on DAGs. In terms of positive results, we present two algorithms that solve  optimally on directed series-parallel graphs (DSPs): a simple linear-time algorithm for the special case of unit edge capacities and a cubic-time dynamic programming algorithm for the general case of non-uniform edge capacities. Further, we introduce the family of laminar series-parallel graphs (LSPs), a generalization of DSPs that also includes cyclic and very dense graphs. Their properties allow us to solve  on LSPs by employing our DSP-algorithms as subroutines. In addition, we give a separate quadratic-time algorithm for  on LSPs with unit edge capacities that also yields straightforward quadratic time algorithms for several related problems such as  and  on LSPs.\n                  <\/jats:p>","DOI":"10.1007\/s00236-024-00475-7","type":"journal-article","created":{"date-parts":[[2025,1,28]],"date-time":"2025-01-28T02:03:20Z","timestamp":1738029800000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Directed capacity-preserving subgraphs: hardness and exact polynomial algorithms"],"prefix":"10.1007","volume":"62","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4681-5550","authenticated-orcid":false,"given":"Markus","family":"Chimani","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4532-3829","authenticated-orcid":false,"given":"Max","family":"Ilsen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,1,28]]},"reference":[{"key":"475_CR1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2020.100253","volume":"37","author":"AR Ahmed","year":"2020","unstructured":"Ahmed, A.R., Bodwin, G., Sahneh, F.D., et al.: Graph spanners: a tutorial review. Comput. Sci. Rev. 37, 100253 (2020). https:\/\/doi.org\/10.1016\/j.cosrev.2020.100253","journal-title":"Comput. Sci. Rev."},{"issue":"2","key":"475_CR2","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1137\/0201008","volume":"1","author":"AV Aho","year":"1972","unstructured":"Aho, A.V., Garey, M.R., Ullman, J.D.: The transitive reduction of a directed graph. SIAM J. Comput. 1(2), 131\u2013137 (1972). https:\/\/doi.org\/10.1137\/0201008","journal-title":"SIAM J. Comput."},{"key":"475_CR3","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF02189308","volume":"9","author":"I Alth\u00f6fer","year":"1993","unstructured":"Alth\u00f6fer, I., Das, G., Dobkin, D.P., et al.: On sparse spanners of weighted graphs. Discret. Comput. Geom. 9, 81\u2013100 (1993). https:\/\/doi.org\/10.1007\/BF02189308","journal-title":"Discret. Comput. Geom."},{"issue":"3631","key":"475_CR4","first-page":"1","volume":"0907","author":"R Andersen","year":"2009","unstructured":"Andersen, R., Feige, U.: Interchanging distance and capacity in probabilistic mappings. CoRR arxiv 0907(3631), 1\u201316 (2009)","journal-title":"CoRR arxiv"},{"key":"475_CR5","doi-asserted-by":"publisher","unstructured":"Andoni, A., Gupta, A., Krauthgamer, R.: Towards (1 + $$\\varepsilon $$)-approximate flow sparsifiers. In: Proceedings of SODA 2014. pp. 279\u2013293, SIAM, Philadelphia (2014). https:\/\/doi.org\/10.1137\/1.9781611973402.20","DOI":"10.1137\/1.9781611973402.20"},{"key":"475_CR6","doi-asserted-by":"publisher","unstructured":"Bencz\u00far, A.A., Karger, D.R.: Approximating s-t minimum cuts in $$\\tilde{O}(n^2)$$ time. In: Proceedings of STOC 1996. pp. 47\u201355, ACM, New York (1996). https:\/\/doi.org\/10.1145\/237814.237827","DOI":"10.1145\/237814.237827"},{"issue":"2","key":"475_CR7","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1137\/070705970","volume":"44","author":"AA Bencz\u00far","year":"2015","unstructured":"Bencz\u00far, A.A., Karger, D.R.: Randomized approximation schemes for cuts and flows in capacitated graphs. SIAM J. Comput. 44(2), 290\u2013319 (2015). https:\/\/doi.org\/10.1137\/070705970","journal-title":"SIAM J. Comput."},{"key":"475_CR8","doi-asserted-by":"publisher","unstructured":"Berman, P, DasGupta, B., Karpinski, M.: Approximating transitive reductions for directed networks. In: Proceedings of WADS 2009, LNCS, vol. 5664. pp. 74\u201385, Springer (2009). https:\/\/doi.org\/10.1007\/978-3-642-03367-4_7","DOI":"10.1007\/978-3-642-03367-4_7"},{"key":"475_CR9","doi-asserted-by":"publisher","unstructured":"Cen, R., Cheng, Y., Panigrahi, D,. et\u00a0al.: Sparsification of directed graphs via cut balance. In: Proceedings ICALP 2021, LIPIcs, vol. 198. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, pp. 45:1\u201345:21, Wadern, Germany (2021)https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2021.45","DOI":"10.4230\/LIPIcs.ICALP.2021.45"},{"key":"475_CR10","doi-asserted-by":"publisher","unstructured":"Chiaraviglio, L., Mellia, M., Neri, F.: Reducing power consumption in backbone networks. In: Proceedings of ICC 2009. pp. 1\u20136, IEEE, Piscataway, NJ (2009). https:\/\/doi.org\/10.1109\/ICC.2009.5199404","DOI":"10.1109\/ICC.2009.5199404"},{"issue":"1","key":"475_CR11","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/J.JCTB.2011.05.001","volume":"102","author":"M Chudnovsky","year":"2012","unstructured":"Chudnovsky, M., Fradkin, A.O., Seymour, P.D.: Tournament immersion and cutwidth. J. Comb. Theory Ser B 102(1), 93\u2013101 (2012). https:\/\/doi.org\/10.1016\/J.JCTB.2011.05.001","journal-title":"J. Comb. Theory Ser B"},{"key":"475_CR12","unstructured":"Cisco.: Cisco annual internet report (2018\u20132023) (2020). https:\/\/www.cisco.com\/c\/en\/us\/solutions\/collateral\/executive-perspectives\/annual-internet-report\/white-paper-c11-741490.pdf"},{"key":"475_CR13","doi-asserted-by":"publisher","unstructured":"Cohen, M.B., Kelner, J.A., Peebles, J., et\u00a0al.: Almost-linear-time algorithms for markov chains and new spectral primitives for directed graphs. In: Proceedings of STOC 2017. pp. 410\u2013419, ACM, New York, NY (2017) https:\/\/doi.org\/10.1145\/3055399.3055463","DOI":"10.1145\/3055399.3055463"},{"key":"475_CR14","doi-asserted-by":"publisher","unstructured":"Cohen, M.B., Kelner, J.A., Kyng, R., et\u00a0al.: Solving directed laplacian systems in nearly-linear time through sparse LU factorizations. In: Proceedings of FOCS 2018. pp 898\u2013909. IEEE Computer Society, Washington (2018). https:\/\/doi.org\/10.1109\/FOCS.2018.00089","DOI":"10.1109\/FOCS.2018.00089"},{"issue":"1","key":"475_CR15","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/BF02109865","volume":"2","author":"G Dahl","year":"1993","unstructured":"Dahl, G.: The design of survivable directed networks. Telecommun. Syst. 2(1), 349\u2013377 (1993). https:\/\/doi.org\/10.1007\/BF02109865","journal-title":"Telecommun. Syst."},{"issue":"2","key":"475_CR16","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0166-218X(93)90086-4","volume":"47","author":"G Dahl","year":"1993","unstructured":"Dahl, G.: Directed steiner problems with connectivity constraints. Discret. Appl. Math. 47(2), 109\u2013128 (1993). https:\/\/doi.org\/10.1016\/0166-218X(93)90086-4","journal-title":"Discret. Appl. Math."},{"key":"475_CR17","doi-asserted-by":"publisher","unstructured":"Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: Proceedings of STOC 2014, pp. 624\u2013633. ACM, New York (2014). https:\/\/doi.org\/10.1145\/2591796.2591884","DOI":"10.1145\/2591796.2591884"},{"issue":"2","key":"475_CR18","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). https:\/\/doi.org\/10.1016\/0022-247X(65)90125-3","journal-title":"J. Math. Anal. Appl."},{"issue":"4","key":"475_CR19","doi-asserted-by":"publisher","first-page":"1239","DOI":"10.1137\/130908440","volume":"43","author":"M Englert","year":"2014","unstructured":"Englert, M., Gupta, A., Krauthgamer, R., et al.: Vertex sparsifiers: new results from old techniques. SIAM J. Comput. 43(4), 1239\u20131262 (2014). https:\/\/doi.org\/10.1137\/130908440","journal-title":"SIAM J. Comput."},{"issue":"5","key":"475_CR20","doi-asserted-by":"publisher","first-page":"1035","DOI":"10.1109\/JPROC.2012.2182970","volume":"100","author":"R Essiambre","year":"2012","unstructured":"Essiambre, R., Tkach, R.W.: Capacity trends and limits of optical communication networks. Proc. IEEE 100(5), 1035\u20131055 (2012). https:\/\/doi.org\/10.1109\/JPROC.2012.2182970","journal-title":"Proc. IEEE"},{"key":"475_CR21","doi-asserted-by":"publisher","unstructured":"Feldmann, A., Gasser, O., Lichtblau, F., et\u00a0al.: The lockdown effect: Implications of the COVID-19 pandemic on internet traffic. In: IMC \u201920. ACM, pp. 1\u201318. New York (2020). https:\/\/doi.org\/10.1145\/3419394.3423658","DOI":"10.1145\/3419394.3423658"},{"key":"475_CR22","doi-asserted-by":"publisher","unstructured":"Flum, J., Grohe, M.: Parameterized complexity theory. In: Texts in Theoretical Computer Science. An EATCS Series, Springer, Berlin (2006). https:\/\/doi.org\/10.1007\/3-540-29953-X","DOI":"10.1007\/3-540-29953-X"},{"key":"475_CR23","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/J.DAM.2013.10.038","volume":"168","author":"R Ganian","year":"2014","unstructured":"Ganian, R., Hlinen\u00fd, P., Kneis, J., et al.: Digraph width measures in parameterized algorithmics. Discret. Appl. Math. 168, 88\u2013107 (2014). https:\/\/doi.org\/10.1016\/J.DAM.2013.10.038","journal-title":"Discret. Appl. Math."},{"key":"475_CR24","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1016\/J.JCTB.2015.09.001","volume":"116","author":"R Ganian","year":"2016","unstructured":"Ganian, R., Hlinen\u00fd, P., Kneis, J., et al.: Are there any good digraph width measures? J Comb Theory Ser B 116, 250\u2013286 (2016). https:\/\/doi.org\/10.1016\/J.JCTB.2015.09.001","journal-title":"J Comb Theory Ser B"},{"key":"475_CR25","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H, Freeman, San Francisco (1979)"},{"issue":"1","key":"475_CR26","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/s004930170004","volume":"21","author":"K Jain","year":"2001","unstructured":"Jain, K.: A factor 2 approximation algorithm for the generalized steiner network problem. Comb 21(1), 39\u201360 (2001). https:\/\/doi.org\/10.1007\/s004930170004","journal-title":"Comb"},{"key":"475_CR27","doi-asserted-by":"publisher","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Proceedings of COCO 1972. The IBM Research Symposia Series, pp. 85\u2013103. Plenum Press, New York (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"1","key":"475_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/net.20072","volume":"46","author":"H Kerivin","year":"2005","unstructured":"Kerivin, H., Mahjoub, A.R.: Design of survivable networks: A survey. Networks 46(1), 1\u201321 (2005). https:\/\/doi.org\/10.1002\/net.20072","journal-title":"Networks"},{"issue":"4","key":"475_CR29","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1137\/S0097539793256685","volume":"24","author":"S Khuller","year":"1995","unstructured":"Khuller, S., Raghavachari, B., Young, N.E.: Approximating the Minimum Equivalent Digraph. SIAM J. Comput. 24(4), 859\u2013872 (1995). https:\/\/doi.org\/10.1137\/S0097539793256685","journal-title":"SIAM J. Comput."},{"issue":"4","key":"475_CR30","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1002\/NET.20005","volume":"43","author":"V Melkonian","year":"2004","unstructured":"Melkonian, V., Tardos, \u00c9.: Algorithms for a network design problem with crossing supermodular demands. Networks 43(4), 256\u2013265 (2004). https:\/\/doi.org\/10.1002\/NET.20005","journal-title":"Networks"},{"key":"475_CR31","doi-asserted-by":"publisher","unstructured":"Moitra, A.: Approximation algorithms for multicommodity-type problems with guarantees independent of the graph size. In: Proceedings of FOCS 2009, pp. 3\u201312. IEEE Computer Society, Washington (2009). https:\/\/doi.org\/10.1109\/FOCS.2009.28","DOI":"10.1109\/FOCS.2009.28"},{"key":"475_CR32","doi-asserted-by":"publisher","first-page":"221","DOI":"10.4086\/toc.2015.v011a007","volume":"11","author":"D Moshkovitz","year":"2015","unstructured":"Moshkovitz, D.: The projection games conjecture and the np-hardness of ln n-approximating set-cover. Theory Comput. 11, 221\u2013235 (2015). https:\/\/doi.org\/10.4086\/toc.2015.v011a007","journal-title":"Theory Comput."},{"issue":"4","key":"475_CR33","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/0020-0190(79)90023-1","volume":"8","author":"J Plesn\u00edk","year":"1979","unstructured":"Plesn\u00edk, J.: The np-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two. Inf. Process. Lett. 8(4), 199\u2013201 (1979). https:\/\/doi.org\/10.1016\/0020-0190(79)90023-1","journal-title":"Inf. Process. Lett."},{"key":"475_CR34","doi-asserted-by":"publisher","unstructured":"R\u00e4cke, H.: Optimal hierarchical decompositions for congestion minimization in networks. In: Proceedings of STOC 2008. pp. 255\u2013264, ACM, New York (2008). https:\/\/doi.org\/10.1145\/1374376.1374415","DOI":"10.1145\/1374376.1374415"},{"key":"475_CR35","unstructured":"Rehs, C.: Comparing and computing parameters for directed graphs. PhD thesis, University of D\u00fcsseldorf, Germany (2022) https:\/\/docserv.uni-duesseldorf.de\/servlets\/DocumentServlet?id=59254"},{"issue":"2","key":"475_CR36","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1002\/net.3230150207","volume":"15","author":"MB Richey","year":"1985","unstructured":"Richey, M.B., Parker, R.G., Rardin, R.L.: An efficiently solvable case of the minimum weight equivalent subgraph problem. Networks 15(2), 217\u2013228 (1985). https:\/\/doi.org\/10.1002\/net.3230150207","journal-title":"Networks"},{"issue":"4","key":"475_CR37","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1137\/0203021","volume":"3","author":"S Sahni","year":"1974","unstructured":"Sahni, S.: Computationally related problems. SIAM J. Comput. 3(4), 262\u2013279 (1974). https:\/\/doi.org\/10.1137\/0203021","journal-title":"SIAM J. Comput."},{"issue":"4","key":"475_CR38","doi-asserted-by":"publisher","first-page":"1851","DOI":"10.1109\/TNET.2018.2854610","volume":"26","author":"T Sch\u00fcller","year":"2018","unstructured":"Sch\u00fcller, T., Aschenbruck, N., Chimani, M., et al.: Traffic engineering using segment routing and considering requirements of a carrier IP network. IEEE\/ACM Trans. Netw. 26(4), 1851\u20131864 (2018). https:\/\/doi.org\/10.1109\/TNET.2018.2854610","journal-title":"IEEE\/ACM Trans. Netw."},{"issue":"4","key":"475_CR39","doi-asserted-by":"publisher","first-page":"981","DOI":"10.1137\/08074489X","volume":"40","author":"DA Spielman","year":"2011","unstructured":"Spielman, D.A., Teng, S.: Spectral sparsification of graphs. SIAM J. Comput. 40(4), 981\u20131025 (2011). https:\/\/doi.org\/10.1137\/08074489X","journal-title":"SIAM J. Comput."},{"issue":"2","key":"475_CR40","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1137\/0211023","volume":"11","author":"J Valdes","year":"1982","unstructured":"Valdes, J., Tarjan, R.E., Lawler, E.L.: The recognition of series parallel digraphs. SIAM J. Comput. 11(2), 298\u2013313 (1982). https:\/\/doi.org\/10.1137\/0211023","journal-title":"SIAM J. Comput."},{"key":"475_CR41","doi-asserted-by":"publisher","unstructured":"Vetta, A.: Approximating the minimum strongly connected subgraph via a matching lower bound. In: Proceedings of SODA 2001, pp. 417\u2013426. ACM\/SIAM, USA (2001). https:\/\/doi.org\/10.5555\/365411.365493","DOI":"10.5555\/365411.365493"},{"issue":"2","key":"475_CR42","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1002\/net.21997","volume":"77","author":"RT Wong","year":"2021","unstructured":"Wong, R.T.: Telecommunications network design: technology impacts and future directions. Networks 77(2), 205\u2013224 (2021). https:\/\/doi.org\/10.1002\/net.21997","journal-title":"Networks"},{"key":"475_CR43","doi-asserted-by":"publisher","unstructured":"Zhang, M., Yi, C., Liu, B., et\u00a0al.: GreenTE: Power-aware traffic engineering. In: Procedings of ICNP 2010, pp. 21\u201330. IEEE Computer Society, Washington (2010). https:\/\/doi.org\/10.1109\/ICNP.2010.5762751","DOI":"10.1109\/ICNP.2010.5762751"},{"key":"475_CR44","doi-asserted-by":"publisher","unstructured":"Zhang, Y., Zhao, Z., Feng, Z.: Towards scalable spectral sparsification of directed graphs. In: Proceedings of ICESS 2019, pp. 1\u20132. IEEE, Piscataway (2019). https:\/\/doi.org\/10.1109\/ICESS.2019.8782449","DOI":"10.1109\/ICESS.2019.8782449"},{"issue":"2","key":"475_CR45","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/S0020-0190(02)00476-3","volume":"86","author":"L Zhao","year":"2003","unstructured":"Zhao, L., Nagamochi, H., Ibaraki, T.: A linear time 5\/3-approximation for the minimum strongly-connected spanning subgraph problem. Inf. Process. Lett. 86(2), 63\u201370 (2003). https:\/\/doi.org\/10.1016\/S0020-0190(02)00476-3","journal-title":"Inf. Process. Lett."}],"updated-by":[{"DOI":"10.1007\/s00236-025-00493-z","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T00:00:00Z","timestamp":1751587200000}}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-024-00475-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-024-00475-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-024-00475-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T01:44:34Z","timestamp":1751593474000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-024-00475-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,28]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["475"],"URL":"https:\/\/doi.org\/10.1007\/s00236-024-00475-7","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,28]]},"assertion":[{"value":"27 March 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 December 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 January 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 July 2025","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The original online version of this article was revised: due to the missing author\u2019s corrections in the article","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 July 2025","order":7,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":8,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published:","order":9,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s00236-025-00493-z","URL":"https:\/\/doi.org\/10.1007\/s00236-025-00493-z","order":10,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"A preliminary version of this paper\u2014without any of the proofs in Sect.\u00a0\n                      \n                      and only considering unit capacities (i.e.,\n                      \n                      )\u2014appeared at the 34th International Workshop on Combinatorial Algorithms (IWOCA 2023).","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Expansion of previous work:"}}],"article-number":"10"}}