pith. sign in

arxiv: 2605.00277 · v1 · submitted 2026-04-30 · 💻 cs.DS

Brief announcement: A special case of maximum flow over time with network changes

Shuchi Chawla , Kristin Sheridan This is my paper

Pith reviewed 2026-05-09 19:26 UTC · model grok-4.3

classification 💻 cs.DS
keywords maximum flow over timetime-expanded networkscondensed networksdynamic capacitiesnetwork flowsdiscrete changes
0
0 comments X

The pith

A condensed time-expanded network with O(n²μ) nodes has the same maximum flow value as the original network with discrete capacity changes.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper considers the maximum flow over time problem on networks with uniform edge lengths where capacities change only at a discrete set of μ critical times. It shows that a specially condensed time-expanded network can be built whose ordinary maximum flow equals the desired time-dependent flow value. With this reduction the problem reduces to running a standard max-flow algorithm on a graph whose size is polynomial in n, m, and μ. This is useful precisely when the number of capacity-change instants is large, because the μ factors then dominate the running time but remain polynomial overall.

Core claim

We show how to construct a condensed version of a Time Expanded Network (cTEN) whose standard max flow value is the same as the max flow over time on the original network. In particular, for a graph with n nodes, m edges, and μ critical times where some edge capacity changes, we obtain a cTEN with O(n²μ) nodes and O(μmn) edges. This implies that the problem can be solved in O(μ²n³m) time using the combinatorial max flow algorithm of Orlin, or in O(μ^(1+o(1))(nm)^(1+o(1))log(UT)) time using the algorithm of Chen et al.

What carries the argument

The condensed Time Expanded Network (cTEN), formed by merging time layers at the μ critical change points so that the resulting static graph yields exactly the same maximum flow as the full time-expanded version.

If this is right

  • The maximum flow over time value equals the ordinary maximum flow computed on the cTEN.
  • Orlin's algorithm yields an O(μ² n³ m) time solution for the dynamic problem.
  • Faster nearly-linear-time max-flow methods give an O(μ^(1+o(1))(nm)^(1+o(1)) log(UT)) bound.
  • The method is intended for instances in which μ is large enough that the μ factors dominate the input size.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same condensation idea may be reusable for other objectives such as minimum-cost flow over time when changes remain discrete.
  • It suggests that many time-dependent flow problems become tractable once the number of distinct change instants is treated as a separate parameter.
  • For networks whose capacities change continuously rather than at discrete instants, a different reduction would be needed.

Load-bearing premise

Edge lengths are all equal and capacity changes occur only at a finite discrete collection of μ critical times.

What would settle it

Any small explicit network with uniform lengths and two or three capacity-change times where the maximum flow computed on the constructed cTEN differs from the true maximum flow over time would disprove the equality claim.

Figures

Figures reproduced from arXiv: 2605.00277 by Kristin Sheridan, Shuchi Chawla.

Figure 3
Figure 3. Figure 3: The collapsed nodes in the cTEN merge nodes representing times between 1 and 3, and as a result the min cut value of the condensed network is much larger than that of the full network. The critical breakpoints of a network Having established the basic structure of cuts in a TEN, we now identify a small set of times that contains all of the critical times of some min cut of TEN(N, T). Such a small set A can… view at source ↗
read the original abstract

We consider the problem of finding the value of a maximum flow over time in a network with uniform edge lengths where the edge capacities change at specific time instants. To solve this problem, we show how to construct a condensed version of a Time Expanded Network (cTEN) whose standard max flow value is the same as the max flow over time on the original network. In particular, for a graph with $n$ nodes, $m$ edges, and $\mu$ {\em critical times} where some edge capacity changes, we obtain a cTEN with $O(n^2\mu)$ nodes and $O(\mu mn)$ edges. This implies that the problem can be solved in $O(\mu^2n^3m)$ time using the combinatorial max flow algorithm of Orlin [Orl13], or in $O(\mu^{(1+o(1))}(nm)^{1+o(1)}\log (UT))$ time using the algorithm of Chen et al. [CKL+22], where $U$ is the maximum capacity of any edge and $T$ is the time horizon. We focus on graphs that experience many time changes across the period of interest, as in such graphs the $\mu$ term dominates the runtime.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The paper considers the maximum flow over time problem in networks with uniform edge lengths where capacities change at μ discrete critical times. It claims to construct a condensed time-expanded network (cTEN) with O(n²μ) nodes and O(μmn) edges whose ordinary max-flow value equals the max flow over time on the original network. This yields solution times of O(μ²n³m) via Orlin's combinatorial algorithm or O(μ^(1+o(1))(nm)^(1+o(1)) log(UT)) via Chen et al., with emphasis on instances where μ dominates.

Significance. If the claimed equivalence holds, the result is significant for efficiently solving this special case of dynamic max-flow without expanding to the full time horizon T. It correctly leverages existing max-flow algorithms (Orlin [Orl13] and Chen et al. [CKL+22]) rather than inventing new ones, and the size bounds replace the usual O(nT) expansion with a μ-dependent construction that can be advantageous when capacity changes are frequent but T is large.

major comments (1)
  1. [Abstract] Abstract: the central claim that the cTEN max-flow value equals the original max flow over time is load-bearing, yet the announcement supplies no construction details, proof sketch, or verification that the condensation (which merges time layers) preserves flow value exactly under the uniform-length and discrete-change assumptions. Without these, the size bounds and equivalence cannot be checked for gaps or hidden assumptions.
minor comments (1)
  1. The abstract states the two resulting time complexities but does not clarify the precise assumptions on U and T needed for the Chen et al. bound or how the cTEN construction interacts with the time horizon.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of our brief announcement and for highlighting the need for greater transparency on the central claim. We address the major comment below.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim that the cTEN max-flow value equals the original max flow over time is load-bearing, yet the announcement supplies no construction details, proof sketch, or verification that the condensation (which merges time layers) preserves flow value exactly under the uniform-length and discrete-change assumptions. Without these, the size bounds and equivalence cannot be checked for gaps or hidden assumptions.

    Authors: We agree that the brief announcement format, by design, presents the result at a high level without full construction details or a proof. The manuscript states that a condensed time-expanded network (cTEN) with the stated size bounds can be constructed such that its ordinary max-flow value equals the max flow over time on the original network under the uniform-length and discrete-change assumptions, but does not include the explicit merging rules for time layers or the equivalence argument. The full construction (which condenses layers by identifying intervals between the μ critical times and routing flows accordingly while preserving conservation and capacity constraints) and the proof of exact equivalence are contained in the complete version of the paper. In the revised announcement we will insert a concise proof sketch (approximately one paragraph) that outlines the condensation procedure and the key invariance that ensures flow value is preserved. revision: yes

Circularity Check

0 steps flagged

No circularity; direct constructive reduction to ordinary max-flow

full rationale

The paper describes an explicit construction of a condensed time-expanded network (cTEN) whose node/edge count is bounded by O(n²μ) and O(μmn) respectively, such that the value of a standard max-flow computation on the cTEN equals the max-flow-over-time value on the input. This is a one-way reduction that invokes no fitted parameters, no self-referential definitions, and no load-bearing self-citations. The only external references are to Orlin and Chen et al. for solving the resulting static max-flow instance; those citations are independent of the present construction. The size bounds and equivalence claim are therefore self-contained and do not reduce to the inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claim rests on standard flow-network axioms plus the domain restriction to uniform lengths and discrete capacity changes. No free parameters, invented entities, or ad-hoc axioms are introduced.

axioms (2)
  • standard math Flow networks obey non-negative capacities, flow conservation at intermediate nodes, and capacity constraints on edges.
    Implicit in the definition of the maximum-flow problem.
  • domain assumption All edges have identical traversal times and capacity values change only at a finite set of discrete instants.
    Explicitly stated as the special case under consideration.

pith-pipeline@v0.9.0 · 5520 in / 1300 out tokens · 42831 ms · 2026-05-09T19:26:14.749378+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

78 extracted references · 32 canonical work pages

  1. [1]

    Proceedings of the 17th ACM Workshop on Hot Topics in Networks , pages =

    Handley, Mark , title =. Proceedings of the 17th ACM Workshop on Hot Topics in Networks , pages =. 2018 , isbn =. doi:10.1145/3286062.3286075 , abstract =

    work page doi:10.1145/3286062.3286075 2018

  2. [2]

    Proceedings of the 2004 Conference on Applications, Technologies, Architectures and Protocols for Computer Communications , year =

    Jain, Sushant and Fall, Kevin and Patra, Rabin , title =. Proceedings of the 2004 Conference on Applications, Technologies, Architectures and Protocols for Computer Communications , year =. doi:10.1145/1015467.1015484 , pages =

    work page doi:10.1145/1015467.1015484 2004

  3. [3]

    1988 , isbn =

    Orlin, James , title =. 1988 , isbn =. doi:10.1145/62212.62249 , booktitle =

    work page doi:10.1145/62212.62249 1988

  4. [4]

    , title =

    Orlin, James B. , title =. 2013 , isbn =. doi:10.1145/2488608.2488705 , booktitle =

    work page doi:10.1145/2488608.2488705 2013

  5. [5]

    2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Maximum flow and minimum-cost flow in almost-linear time , author=. 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2022 , organization=

    2022

  6. [6]

    Orlin , title =

    Satoru Iwata and James B. Orlin , title =. Proceedings of the 2009 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , chapter =. doi:10.1137/1.9781611973068.133 , URL =. https://epubs.siam.org/doi/pdf/10.1137/1.9781611973068.133 , year=

    work page doi:10.1137/1.9781611973068.133 2009

  7. [7]

    Proceedings of the tenth annual ACM symposium on Theory of computing , pages=

    Combinatorial optimization with rational objective functions , author=. Proceedings of the tenth annual ACM symposium on Theory of computing , pages=

  8. [8]

    Proceedings of the eighteenth annual symposium on Computational geometry , pages=

    Parametric search made practical , author=. Proceedings of the eighteenth annual symposium on Computational geometry , pages=

  9. [9]

    2019 , url =

    Jeff Erickson , title =. 2019 , url =

    2019

  10. [11]

    Networks , volume=

    A fast maximum flow algorithm , author=. Networks , volume=. 2021 , publisher=

    2021

  11. [12]

    30th Annual Symposium on Foundations of Computer Science , pages=

    A new algorithm for minimizing convex functions over convex sets , author=. 30th Annual Symposium on Foundations of Computer Science , pages=. 1989 , organization=

    1989

  12. [13]

    2015 IEEE 56th Annual Symposium on Foundations of Computer Science , pages=

    A faster cutting plane method and its implications for combinatorial and convex optimization , author=. 2015 IEEE 56th Annual Symposium on Foundations of Computer Science , pages=. 2015 , organization=

    2015

  13. [14]

    Convex minimization with integer minima in

    Jiang, Haotian and Lee, Yin Tat and Song, Zhao and Zhang, Lichen , booktitle=. Convex minimization with integer minima in. 2024 , organization=

    2024

  14. [15]

    Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , chapter =

    Miriam Schl\"oter and Martin Skutella , title =. Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , chapter =. doi:10.1137/1.9781611974782.52 , year=

    work page doi:10.1137/1.9781611974782.52 2017

  15. [16]

    The quickest transshipment problem

    Hoppe, Bruce and Tardos, \'. “The quickest transshipment problem” , year =. Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms , pages =

  16. [17]

    1978 , isbn =

    Megiddo, Nimrod , title =. 1978 , isbn =. doi:10.1145/800133.804326 , booktitle =

    work page doi:10.1145/800133.804326 1978

  17. [18]

    Parametric search made practical , year =

    van Oostrum, Ren\'. Parametric search made practical , year =. doi:10.1145/513400.513401 , booktitle =

    work page doi:10.1145/513400.513401

  18. [19]

    Efficient Dynamic Network Flow Algorithms , author =

  19. [20]

    Temporal flows in temporal networks , volume =

    Akrida, Eleni and Czyzowicz, Jurek and Gasieniec, Leszek and Kuszner, Łukasz and Spirakis, Paul , year =. Temporal flows in temporal networks , volume =. Journal of Computer and System Sciences , doi =

  20. [21]

    Multigraph-Based Routing in Delay Tolerant Networks: An Alternative to Contact Graph Routing , year=

    Hylton, Alan and Moy, Michael and Kassouf-Short, Robert and Cleveland, Jacob , booktitle=. Multigraph-Based Routing in Delay Tolerant Networks: An Alternative to Contact Graph Routing , year=

  21. [22]

    Fraire and Olivier

    Juan A. Fraire and Olivier. Routing in the Space Internet: A contact graph routing tutorial , journal =. 2021 , issn =. doi:https://doi.org/10.1016/j.jnca.2020.102884 , url =

    work page doi:10.1016/j.jnca.2020.102884 2021

  22. [23]

    Contact Multigraph Routing: Overview and Implementation , year=

    Moy, Michael and Kassouf-Short, Robert and Kortas, Nadia and Cleveland, Jacob and Tomko, Brian and Conricode, Dominic and Kirkpatrick, Yael and Cardona, Robert and Heller, Brian and Curry, Justin , booktitle=. Contact Multigraph Routing: Overview and Implementation , year=

  23. [24]

    , booktitle=

    Hajek, Bruce and Ogier, Richard G. , booktitle=. Optimal dynamic routing in communication networks with continuous traffic , year=

  24. [25]

    and Tarjan, Robert E

    Gallo, Giorgio and Grigoriadis, Michael D. and Tarjan, Robert E. , title =. SIAM Journal on Computing , volume =. 1989 , doi =

    1989

  25. [26]

    Networks , volume =

    Saho, Masahide and Shigeno, Maiko , title =. Networks , volume =. doi:https://doi.org/10.1002/net.21726 , url =. https://onlinelibrary.wiley.com/doi/pdf/10.1002/net.21726 , year =

    work page doi:10.1002/net.21726

  26. [27]

    On the Quickest Flow Problem in Dynamic Networks – A Parametric Min-Cost Flow Approach , booktitle =

    Lin, Maokai and Jaillet, Patrick , year =. On the Quickest Flow Problem in Dynamic Networks – A Parametric Min-Cost Flow Approach , booktitle =

  27. [28]

    , title =

    Ogier, Richard G. , title =. Networks , volume =. doi:https://doi.org/10.1002/net.3230180405 , url =. https://onlinelibrary.wiley.com/doi/pdf/10.1002/net.3230180405 , year =

    work page doi:10.1002/net.3230180405

  28. [29]

    Universally Maximum Flow with Piecewise-Constant Capacities

    Fleischer, Lisa. Universally Maximum Flow with Piecewise-Constant Capacities. Integer Programming and Combinatorial Optimization. 1999

    1999

  29. [30]

    and Cai, X

    Sha, D. and Cai, X. and Wong, C. K. The Maximum Flow in a Time-Varying Network. Optimization: Proceedings of the 9th Belgian-French-German Conference on Optimization Namur, September 7--11, 1998. 2000. doi:10.1007/978-3-642-57014-8_29

    work page doi:10.1007/978-3-642-57014-8_29 1998

  30. [31]

    2003 , institution=

    A linear programming formulation of flows over time with piecewise constant capacity and transit times , author=. 2003 , institution=

    2003

  31. [32]

    The Quickest Transshipment Problem , urldate =

    Bruce Hoppe and Eva Tardos , journal =. The Quickest Transshipment Problem , urldate =

  32. [33]

    , title =

    Fleischer, Lisa K. , title =. SIAM Journal on Optimization , volume =. 2001 , doi =

    2001

  33. [34]

    Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , year=

    Miriam Schlöter and Martin Skutella and Khai Van Tran , title =. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , year=. doi:10.1137/1.9781611977073.5 , URL =

    work page doi:10.1137/1.9781611977073.5 2022

  34. [35]

    A note on the quickest minimum cost transshipment problem , journal =

    Martin Skutella , keywords =. A note on the quickest minimum cost transshipment problem , journal =. 2023 , issn =. doi:https://doi.org/10.1016/j.orl.2023.03.005 , url =

    work page doi:10.1016/j.orl.2023.03.005 2023

  35. [36]

    NP-hardness of shortest path problems in networks with non-FIFO time-dependent travel times , journal =

    Tim Zeitz , keywords =. NP-hardness of shortest path problems in networks with non-FIFO time-dependent travel times , journal =. 2023 , issn =. doi:https://doi.org/10.1016/j.ipl.2022.106287 , url =

    work page doi:10.1016/j.ipl.2022.106287 2023

  36. [37]

    An Introduction to Network Flows over Time

    Skutella, Martin. An Introduction to Network Flows over Time. Research Trends in Combinatorial Optimization: Bonn 2008. 2009. doi:10.1007/978-3-540-76796-1_21

    work page doi:10.1007/978-3-540-76796-1_21 2008

  37. [38]

    Multicommodity flows over time: Efficient algorithms and complexity , journal =

    Alex Hall and Steffen Hippler and Martin Skutella , keywords =. Multicommodity flows over time: Efficient algorithms and complexity , journal =. 2007 , note =. doi:https://doi.org/10.1016/j.tcs.2007.02.046 , url =

    work page doi:10.1016/j.tcs.2007.02.046 2007

  38. [39]

    Graph orientation and flows over time , journal =

    Arulselvan, Ashwin and Gro. Graph orientation and flows over time , journal =. 2015 , doi =

    2015

  39. [40]

    Theory Comput

    Koch, Ronald and Skutella, Martin , title =. Theory Comput. Syst. , volume =. 2011 , doi =

    2011

  40. [41]

    Koch, Ronald and Nasrabadi, Ebrahim and Skutella, Martin , title =. Math. Methods Oper. Res. , volume =. 2011 , doi =

    2011

  41. [42]

    Maximum Multicommodity Flows over Time without Intermediate Storage , booktitle =

    Gro. Maximum Multicommodity Flows over Time without Intermediate Storage , booktitle =. 2012 , doi =

    2012

  42. [43]

    SIAM Journal on Computing , volume =

    Fleischer, Lisa and Skutella, Martin , title =. SIAM Journal on Computing , volume =. 2007 , doi =

    2007

  43. [44]

    Schmidt, Melanie and Skutella, Martin , title =. Discret. Appl. Math. , volume =. 2014 , doi =

    2014

  44. [45]

    ATMOS 2018 – Proc

    Sering, Leon and Skutella, Martin , title =. ATMOS 2018 – Proc. 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems , pages =. 2018 , doi =

    2018

  45. [46]

    2021 , isbn =

    Sering, Leon and Vargas Koch, Laura and Ziemke, Theresa , title =. 2021 , isbn =. doi:10.1145/3465456.3467626 , booktitle =

    work page doi:10.1145/3465456.3467626 2021

  46. [47]

    E. J. Anderson and P. Nash and A. B. Philpott , journal =. A Class of Continuous Network Flow Problems , urldate =

  47. [48]

    A Survey of Mathematical Structures for Lunar Networks , year=

    Hylton, Alan and Short, Robert and Cleveland, Jacob and Freides, Olivia and Memon, Zander and Cardona, Robert and Green, Robert and Curry, Justin and Gopalakrishnan, Sriram and Dabke, Devavrat Vivek and Story, Brittany and Moy, Michael and Mallery, Brendan , booktitle=. A Survey of Mathematical Structures for Lunar Networks , year=

  48. [49]

    Quickest flow over time network interdiction: mathematical formulation and a solution method , volume =

    Morowati-Shalilvand, Shahram and Shahmorad, Sedaghat and Mirnia, Kamal and Mehri-Tekmeh, Javad , year =. Quickest flow over time network interdiction: mathematical formulation and a solution method , volume =. Operational Research , doi =

  49. [50]

    The quickest flow problem

    Burkard, Rainer Ernst and Karin Dlaska and Bettina Klinz. The quickest flow problem. Mathematical Methods of Operations Research. 1993

    1993

  50. [51]

    Fleischer and É

    L. Fleischer and É. Tardos , keywords =. Efficient continuous-time dynamic network flow algorithms , journal =. 1998 , issn =. doi:https://doi.org/10.1016/S0167-6377(98)00037-6 , url =

    work page doi:10.1016/s0167-6377(98)00037-6 1998

  51. [52]

    Canadian journal of Mathematics , volume=

    Maximal flow through a network , author=. Canadian journal of Mathematics , volume=. 1956 , publisher=

    1956

  52. [53]

    L. R. Ford and D. R. Fulkerson , journal =. Constructing Maximal Dynamic Flows from Static Flows , urldate =

  53. [54]

    Generalized Maximum Flows over Time

    Gro , Martin and Skutella, Martin. Generalized Maximum Flows over Time. Approximation and Online Algorithms. 2012

    2012

  54. [55]

    Minimum cost dynamic flows: The series-parallel case

    Klinz, Bettina and Woeginger, Gerhard J. Minimum cost dynamic flows: The series-parallel case. Integer Programming and Combinatorial Optimization. 1995

    1995

  55. [56]

    , title =

    Klinz, Bettina and Woeginger, Gerhard J. , title =. Networks , volume =. doi:https://doi.org/10.1002/net.10112 , url =. https://onlinelibrary.wiley.com/doi/pdf/10.1002/net.10112 , year =

    work page doi:10.1002/net.10112

  56. [57]

    Annals of Operations Research , year=2024, volume=

    Tanka Nath Dhamala and Mohan Chandra Adhikari and Durga Prasad Khanal and Urmila Pyakurel , title=. Annals of Operations Research , year=2024, volume=. doi:10.1007/s10479-023-05773- , url=

    work page doi:10.1007/s10479-023-05773- 2024

  57. [58]

    Cai and D

    X. Cai and D. Sha and C.K. Wong , keywords =. Time-varying universal maximum flow problems , journal =. 2001 , issn =. doi:https://doi.org/10.1016/S0895-7177(00)00252-1 , url =

    work page doi:10.1016/s0895-7177(00)00252-1 2001

  58. [59]

    Journal of Institute of Science and Technology , author=

    Quickest Flow Algorithms with Time-Varying Attributes , volume=. Journal of Institute of Science and Technology , author=. 2021 , month=. doi:10.3126/jist.v26i1.37826 ,number=

    work page doi:10.3126/jist.v26i1.37826 2021

  59. [60]

    On finding paths and flows in multicriteria, stochastic and time-varying networks

    Sathaporn Opasanon. On finding paths and flows in multicriteria, stochastic and time-varying networks. 2004

    2004

  60. [61]

    Tjandra , title =

    Stevanus A. Tjandra , title =. 2001 , url =

    2001

  61. [62]

    and Tarjan, Robert E

    Goldberg, Andrew V. and Tarjan, Robert E. , title =. J. ACM , month = oct, pages =. 1989 , issue_date =. doi:10.1145/76359.76368 , abstract =

    work page doi:10.1145/76359.76368 1989

  62. [63]

    Mathematics of operations research , volume=

    Earliest arrival flows with multiple sources , author=. Mathematics of operations research , volume=. 2009 , publisher=

    2009

  63. [64]

    Mathematical Programming , volume=

    A polynomial time primal network simplex algorithm for minimum cost flows , author=. Mathematical Programming , volume=. 1997 , publisher=

    1997

  64. [65]

    and Tarjan, Robert E

    Goldberg, Andrew V. and Tarjan, Robert E. , title =. Mathematics of Operations Research , volume =. 1990 , doi =. https://doi.org/10.1287/moor.15.3.430 , abstract =

    work page doi:10.1287/moor.15.3.430 1990

  65. [66]

    and Rao, Satish , title =

    Goldberg, Andrew V. and Rao, Satish , title =. J. ACM , month = sep, pages =. 1998 , issue_date =. doi:10.1145/290179.290181 , abstract =

    work page doi:10.1145/290179.290181 1998

  66. [67]

    and Tarjan, Robert E

    Goldberg, Andrew V. and Tarjan, Robert E. , title =. J. ACM , month = oct, pages =. 1988 , issue_date =. doi:10.1145/48014.61051 , abstract =

    work page doi:10.1145/48014.61051 1988

  67. [68]

    Sleator and Robert

    Daniel D. Sleator and Robert. A data structure for dynamic trees , journal =. 1983 , issn =. doi:https://doi.org/10.1016/0022-0000(83)90006-5 , url =

    work page doi:10.1016/0022-0000(83)90006-5 1983

  68. [69]

    The Quickest Multicommodity Flow Problem

    Fleischer, Lisa and Skutella, Martin. The Quickest Multicommodity Flow Problem. Integer Programming and Combinatorial Optimization. 2002

    2002

  69. [70]

    Operations Research , volume =

    Boland, Natashia and Hewitt, Mike and Marshall, Luke and Savelsbergh, Martin , title =. Operations Research , volume =. 2017 , doi =

    2017

  70. [71]

    Stevanus Adrianto Tjandra , title =

  71. [72]

    Maximum flow problem on dynamic generative network flows with time-varying bounds , journal =

    Hassan Salehi Fathabadi and Seyed Ahmad Hosseini , keywords =. Maximum flow problem on dynamic generative network flows with time-varying bounds , journal =. 2010 , issn =. doi:https://doi.org/10.1016/j.apm.2009.10.026 , url =

    work page doi:10.1016/j.apm.2009.10.026 2010

  72. [73]

    , title =

    Edmonds, Jack and Karp, Richard M. , title =. 1972 , issue_date =. doi:10.1145/321694.321699 , journal =

    work page doi:10.1145/321694.321699 1972

  73. [74]

    33rd Annual European Symposium on Algorithms (ESA 2025) , pages =

    Anapolska, Mariia and van den Boom, Dario and B\". 33rd Annual European Symposium on Algorithms (ESA 2025) , pages =. 2025 , volume =. doi:10.4230/LIPIcs.ESA.2025.112 , annote =

    work page doi:10.4230/lipics.esa.2025.112 2025

  74. [75]

    Knuth , title =

    Donald E. Knuth , title =. Commun. 1974 , doi =

    1974

  75. [76]

    Dijkstra , title =

    Edsger W. Dijkstra , title =. Commun. 1968 , doi =

    1968

  76. [77]

    1993 , isbn =

    Jim Gray and Andreas Reuter , title =. 1993 , isbn =

    1993

  77. [78]

    1975 , crossref =

    On Time versus Space and Related Problems , booktitle =. 1975 , crossref =. doi:10.1109/SFCS.1975.23 , timestamp =

    work page doi:10.1109/sfcs.1975.23 1975

  78. [79]

    1975 , timestamp =

    16th Annual Symposium on Foundations of Computer Science, Berkeley, California, USA, October 13-15, 1975 , publisher =. 1975 , timestamp =

    1975