Brief Announcement: A Special Case of Maximum Flow over Time with Network Changes

Chawla, Shuchi; Sheridan, Kristin

doi:10.4230/LIPIcs.SAND.2026.23

Brief Announcement: A Special Case of Maximum Flow over Time with Network Changes

Shuchi Chawla

Department of Computer Science, University of Texas, Austin, TX, USA Kristin Sheridan²²2A part of this research performed while at NASA’s Glenn Research Center, Cleveland, OH, USA

Department of Computer Science, University of Texas, Austin, TX, USA

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 over time. We assume that the capacity of every edge in the network is a piecewise constant function and parameterize the running time of our algorithm by the total number of pieces in the capacity functions across all edges, denoted $\mu$ . The key technical component in our approach is a condensed version of a Time Expanded Network (that we call a cTEN) whose classical max flow value is the same as the max flow over time on the original network. We show that a graph with $n$ nodes, $m$ edges, and $\mu$ capacity changes, admits a cTEN with $O(n^{2}\mu)$ nodes and $O(\mu mn)$ edges. This implies that the problem can be solved in $O(\mu^{2}n^{3}m)$ time using the combinatorial max flow algorithm of Orlin [7], or in $O(\mu^{(1+o(1))}(nm)^{1+o(1)}\log(nUT))$ time using the algorithm of Chen et al. [2], where $U$ is the maximum capacity of any edge and $T$ is the time horizon. When $\mu>>m,n$ , this is faster than previously known algorithms for this problem.

Keywords and phrases:

maximum flow, dynamic flows, flows over time

Funding:

Kristin Sheridan: Additional funding provided by JPMorgan Chase & Co.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Network optimization

Related Version:

Full Version: https://arxiv.org/abs/2605.00277

Funding:

This research was funded in part by NSF awards CCF-2217069 and CCF-2225259.

DOI:

10.4230/LIPIcs.SAND.2026.23

Event:

5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)

Editors:

George B. Mertzios and Andréa W. Richa

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

This paper investigates the maximum flow over time problem in temporal networks.³³3By “temporal” we mean that some network parameters change over time; networks with unchanging parameters are called “static”. Motivated by applications in satellite networks where movement of the satellites causes frequent changes to the network, we study the effect of the number of changes on the computation of a flow over time.⁴⁴4It is important to note that even in static networks (where all network properties stay the same over time), flow over time computation (see, e.g., [8]) can be different from steady-state or classical flow problems (e.g. [3]), as in the former case flow takes time to traverse edges. Our primary question is: Given a temporal network $N$ , a source $s$ , a sink $d$ , and a time $T$ , what is the maximum amount of flow that can be moved from $s$ to $d$ over time horizon $[0,T]$ ? We call this the maximum flow over time problem on temporal networks.

We focus on the special case of a temporal network where all edge lengths are uniform (the same) and static (unchanging over time), but edge capacities change over time. We assume that all edge capacities are piecewise constant, and denote by $\mu$ the total number of changes across all edges. Our primary result is stated in Theorem 1.

Theorem 1.

Let $T>0$ be an integer, and $N=(V,E,\tau,\{u_{ij}\})$ be a temporal network where each edge $ij\in E$ has length $\tau$ and its capacity at time $t\in[T]$ is given by $u_{ij}(t)$ .⁵⁵5For integer $x>0$ , we use $[x]$ to denote the set $\{0,1,\cdots,x\}$ . In particular $[x]$ has $x+1$ elements. We assume that $\tau$ and $u_{ij}(t)$ for all $ij\in E$ and times $t\in[T]$ are integral. Let $\mu_{ij}$ denote the number of pieces in the function $u_{ij}$ over the time horizon $[T]$ , and $\mu=\sum_{ij\in E}\mu_{ij}$ .

Then the maximum $s$ - $d$ flow value on $N$ over time horizon $T$ can be found in time $O(MF(O(n^{2}\mu),O(mn\mu)))$ , where $n=|V|,m=|E|,$ and $MF(n^{\prime},m^{\prime})$ is the runtime for a steady-state (classical) max flow algorithm on a network with $n^{\prime}$ nodes and $m^{\prime}$ edges.

Employing Orlin’s [7] $O(n^{\prime}m^{\prime})$ max flow algorithm, we can achieve a strongly polynomial runtime $O(\mu^{2}n^{3}m)$ . Alternatively, leveraging the algorithm by Chen et al. [2] allows us to solve the problem in $O(\mu^{1+o(1)}(nm)^{1+o(1)}\log(nUT))$ time, where $U$ is the maximum edge capacity at any time. Previous results solve the feasibility variant of this problem (checking if a given flow value is feasible) in strongly polynomial time $O(\mu^{5}\cdot\text{polylog}(\mu))$ or weakly polynomial time $O(\mu^{3+o(1)}\cdot\log^{O(1)}(TU))$ for networks with general edge lengths and piecewise constant capacities [4, 5, 6, 2]. These other techniques can be paired with binary search or parametric search to find the maximum flow value, at a cost of increased runtime, whereas our method directly finds the maximum feasible flow. In the regime where $\mu>>n,m$ (meaning the graph experiences a large number of changes relative to the number of nodes and edges), our approach yields faster runtimes than existing algorithms in both the strongly and weakly polynomial settings, even compared to algorithms that only test feasibility. If for example $n,m=O(\mu^{1/4})$ , our runtimes improve to $O(\mu^{3})$ and $O(\mu^{3/2+o(1)}\log(nTU))$ .

2 Definitions and main result

We begin by formally defining the special class of temporal networks we study.

Definition 2.

A temporal network $N=(V,E,\tau,\{u_{ij}:\mathbb{Z}\rightarrow\mathbb{R}_{\geq 0}\}_{ij\in E})$ consists of

$\blacksquare$

a set of vertices $V$ ,
$\blacksquare$

a set of directed edges $E\subseteq V\times V$ , each of integral length $\tau$ , and
$\blacksquare$

capacity functions $u_{ij}$ for each edge that denote the capacity of edges at each integral time.

Note that a network whose edge capacities are piecewise constant and are nonzero only at times in $[T]$ can be specified in space $\Theta(\mu\cdot\log(U)\cdot\log(T))$ , where $U$ is the maximum capacity of any edge at any time, and $\mu$ is the total number of constant pieces across all capacity functions. In particular, the input size is linear in $\mu$ but logarithmic in $T$ . Our objective is to design algorithms that run in time polynomial in $\mu$ with no dependence on $T$ .

We can now formally define flows over time on temporal networks. A flow $f$ is a vector of functions $f_{ij}$ for $ij\in E$ , where $f_{ij}(t)$ denotes the flow amount carried by edge $i j$ at time $t\in T$ . Let $\eta_{i,f}(t)$ be the net flow into $i$ at time $t$ under flow $f$ . That is, $\eta_{i,f}(t):=\sum_{j:ji\in E}\sum_{t^{\prime}=0}^{t-\tau}f_{ji}(t^{\prime})-% \sum_{j:ij\in E}\sum_{t^{\prime}=0}^{t}f_{ij}(t^{\prime})$ . The value of flow $f$ at over time horizon $T$ is defined to be $\eta_{d,f}(T)$ , where the network sink is $d$ .

Definition 3.

An $s$ - $d$ flow over time $T$ in a network $(V,E,\tau,\{u_{ij}\})$ is a set of functions $f_{ij}:[T]\rightarrow\mathbb{R}_{\geq 0}$ for each $ij\in E$ such that the following hold:

1.

For all integers $t\in[T],ij\in E$ , $f_{ij}(t)\leq u_{ij}(t)$ (edge capacity constraint)
2.

For all $t\in[T],i\in V\setminus\{s\}$ : $\eta_{i,f}(t)\geq 0$ (net flow into a node is always non-negative)
3.

For all $i\in V\setminus\{s,d\}$ : $\eta_{i,f}(T)=0,$ (net flow over the whole period is $0$ for all but $s$ and $d$ )

Time Extended Networks (TENs)

We approach the maximum flow over time problem by reducing to a classical max flow problem. The most basic way to relate these two problems is using a Time Extended Network of the temporal network $N$ over time horizon $T$ , denoted $\textsc{TEN}(N,T)$ . Specifically, $\textsc{TEN}(N,T)$ has vertex set $V\times[T]$ , and there is an edge from $(i,t)$ to $(j,t^{\prime})$ of capacity $u_{ij}(t)$ for $i\neq j$ if and only if $ij\in E$ and $t^{\prime}=t+\tau$ . For all $i\in V,t<T$ , there is also an edge of infinite capacity from $(i,t)$ to $(i,t+1)$ . The source and sink of this network are $(s,0)$ and $(d,T)$ , respectively.

For any $s, d$ and $T$ , the value of a maximum $s$ - $d$ flow over time horizon $[T]$ in $N$ is the same as that of a maximum steady-state $(s,0)$ - $(d,T)$ flow in $\textsc{TEN}(N,T)$ [1]. Thus, one solution to this problem is to run any steady-state max flow algorithm on $\textsc{TEN}(N,T)$ . However, the size of $\textsc{TEN}(N,T)$ can be exponential in the size of $N$ when $T\gg n,m,\mu$ . To avoid this exponential blow up, we define a “compressed” version of $\textsc{TEN}(N,T)$ , which we call a condensed time extended network, or $\textsc{cTEN}(N,A,T)$ (where $A\subseteq[T]$ is a set to be defined). The basic idea is to compress multiple layers of the TEN corresponding to certain intervals of time into a single layer without changing the capacity of the network. The set $A$ defines the appropriate time intervals.

Definition 4.

Let $N=(V,E,\tau,\{u_{ij}\})$ be a temporal network with source $s$ and sink $d$ , and let $A\subseteq[T]$ with $0,T\in A$ . Let $0=t_{1}<t_{2}<\cdots<t_{k}=T$ denote the times in $A$ . We define $\textsc{cTEN}(N,A,T)$ as a classical (steady-state) flow network as follows:

$\blacksquare$

The vertex set is $V^{\prime}:=V\times A$ .
$\blacksquare$

For all $x\in V$ and all $1\leq j<k$ , there is an edge from $(x,t_{j})$ to $(x,t_{j+1})$ with infinite capacity.
$\blacksquare$

For all $xy\in E$ and all $1\leq i,j<k$ , there is an edge from $(x,t_{i})$ to $(y,t_{j})$ with the following capacity if it is non-zero:

$\displaystyle\sum_{\begin{subarray}{c}t:(t_{i}\leq t<t_{i+1}),\\ (t_{j}\leq t+\tau_{ij}<t_{j+1})\end{subarray}}u_{xy}(t).$

Further, we treat $(s,0)$ as the source and $(d,T)$ as the sink. For brevity, we may write $\textsc{cTEN}(N,A)$ if $T$ is clear from the context.

Note that $\textsc{cTEN}(N,[T],T)$ is the same as $\textsc{TEN}(N,T)$ . The size of $\textsc{cTEN}(N,A,T)$ is polynomial in the size of $N$ and $|A|$ , and therefore can be much smaller than the size of $\textsc{TEN}(N,T)$ when $A$ is much smaller than $[T]$ . Furthermore, it is easy to see that $\textsc{cTEN}(N,A,T)$ can be computed efficiently in time polynomial in the size of $N$ and $|A|$ .

Finite cuts and cut functions

Our proof methods primarily involve analyzing minimum cuts on the TEN and cTEN of a network. Note that in $\textsc{TEN}(N,T)$ , if an $(s,0)$ - $(d,T)$ cut $C\subseteq V$ has finite capacity, then $(i,t)\in C\implies(i,t+1)\in C$ for all $i$ and all $t<T$ . We represent finite capacity cuts in a TEN by a cut function that maps every vertex $i\in V$ to the earliest time $t\in[T]$ such that $(i,t)\in C$ , or to $T+1$ if no such time exists.

Definition 5.

A cut function $\phi$ on $\textsc{TEN}(N,T)$ maps vertices $i\in V$ to the interval $[T+1]$ with $\phi(s)=0$ and $\phi(d)=T+1$ , where $s$ is the source and $d$ is the sink. The cut function uniquely represents the $(s,0)$ - $(d,T)$ cut $C_{\phi}$ with $C_{\phi}:=\{(i,t):i\in V,t\in[T],t\geq\phi(i)\}$ . We let $cost(\phi)$ be the cost of the cut defined by $C_{\phi}$ .

We analogously define a cut function $\phi$ on a $\textsc{cTEN}(N,A,T)$ as a map from vertices $i\in V$ to the set $A\cup\{T+1\}$ , that represents the cut $C_{\phi}:=\{(i,t):i\in V,t\in A,t\geq\phi(i)\}$ .

Note that finite capacity cuts in a cTEN form a subset of finite capacity cuts in a TEN. Our goal is to argue that there is a small cTEN that has the same min cut capacity as the TEN. To this end, we focus on identifying the “critical” times corresponding to edges crossing a min cut in the TEN. For a cut function $\phi$ , $\textsc{Range}(\phi):=\{t:\exists i\in V\text{ with }\phi(i)=t\}.$ The following observation then follows from the correspondence between the cut functions of a cTEN and a TEN.

Observation 6.

Let $A\subseteq[T]$ be such that there exists a cut function $\phi$ corresponding to a min $(s,0)$ - $(d,T)$ cut in $\textsc{TEN}(N,T)$ with $\textsc{Range}(\phi)\cap[T]\subseteq A$ . Then, any min $(s,0)$ - $(d,T)$ cut in $\textsc{cTEN}(N,A,T)$ is also a min $s$ - $d$ cut in $\textsc{TEN}(N,T)$ . In particular, the capacity of the min cut in $\textsc{cTEN}(N,A,T)$ is equal to the capacity of the min cut in $\textsc{TEN}(N,T)$ .

The critical times of a network

Having established the basic structure of cuts in a TEN, we now identify a small set that contains all of the critical times of some min cut of $\textsc{TEN}(N,T)$ . Such a small set $A$ can then be used to construct a small cTEN that captures the min cut capacity of the TEN as per Observation 6. Intuitively, we construct our set of critical times to include all times at which some edge changes capacity, as well as certain “offset” times from each such change. The idea is that information about the change in some edge capacity may propagate down a path of nodes in the network, so the offset values should correspond to some possible path length in the network. As $\tau$ is uniform across all edges, all paths in the network have length $\ell\cdot\tau$ for some $\ell\in[0,n]$ . Thus, we define our critical times as follows.

Definition 7.

Given a temporal network $N=(V,E,\tau,\{u_{ij}\})$ , let $\mathcal{T}$ be the set of times at which some $u_{ij}$ changes value: $\mathcal{T}=\{t\in[T]:\exists ij\text{ with }u_{ij}(t)\neq u_{ij}(t-1)\}\cup\{% 0,T,T+1\}$ . Then we define $\textsc{CriticalTimes}(N):=\{\theta\pm\ell\cdot\tau:\theta\in\mathcal{T},\ell% \in[n]\}.$

Note that we have $|\mathcal{T}|\leq\mu+3$ , and therefore, $|\textsc{CriticalTimes}(N)|=O(n\mu)$ . We can now state our main technical lemma, which we discuss further in Section 3.

Lemma 8.

For any $\textsc{TEN}(N,T)$ there exists a cut function $\phi$ corresponding to a min $(s,0)$ - $(d,T)$ cut with $\textsc{Range}(\phi)\subseteq\textsc{CriticalTimes}(N)$ .

Note that Lemma 8 combined with Lemma 6 implies that the maximum $s$ - $d$ flow over $T$ on $N$ is exactly the steady-state maximum flow value on $\textsc{cTEN}(N,A,T)$ , where $A=\textsc{CriticalTimes}(N)\cap[T]$ . Using Lemma 8 and a short argument to bound the size of $\textsc{cTEN}(N,A,T)$ (which we give in the full version of this paper), we get Theorem 1.

3 Finding the value of the max flow

In this section we discuss Lemma 8. Our goal is to show the existence of a min cut $\phi$ in $\textsc{TEN}(N,T)$ with $\textsc{Range}(\phi)\cap[T]\subseteq\textsc{CriticalTimes}(N)$ . We first define a local operation on cuts that allows us to move from one min cut to another. Let $\phi$ denote a cut function in $\textsc{TEN}(N,T)$ . We use $X_{\phi}$ to denote vertices that are mapped to $0$ or $T+1$ in $\phi$ : $X_{\phi}:=\{i\in V:\phi(i)\in\{0,T+1\}\}$ . Then for any subset $C\subseteq V\setminus X_{\phi}$ , we can define two variants of the cut function $\phi$ – one where the assignments to vertices in $C$ move “up” and the other where the assignments move “down”. Formally,

Definition 9.

Given a cut function $\phi$ in $\textsc{TEN}(N,T)$ and a set $C\subseteq V\setminus X_{\phi}$ , define the cut functions $\phi_{C}^{+}$ and $\phi_{C}^{-}$ as follows:

$\blacksquare$

$\phi_{C}^{+}(i):=\phi(i)+1$ if $i\in C$ , and $\phi_{C}^{+}(i):=\phi(i)$ otherwise.
$\blacksquare$

$\phi_{C}^{-}(i):=\phi(i)-1$ if $i\in C$ , and $\phi_{C}^{-}(i):=\phi(i)$ otherwise.

Next we identify properties the set $C$ needs to satisfy to ensure that $\phi_{C}^{+}$ and $\phi_{C}^{-}$ have the same (minimum) capacity as $\phi$ .

Definition 10.

Given a cut function $\phi$ in $\textsc{TEN}(N,T)$ , a set $C\subseteq V\setminus X_{\phi}$ , and some vertex $i\in C$ , define $\texttt{forbidden}_{\phi,C}(i)$ as the union of the following sets:

$\blacksquare$

$\mathcal{T}\cup\{\theta+\tau:\theta\in\mathcal{T}\}$
$\blacksquare$

$\{\phi(j)-\tau,\phi(j):ij\in E\text{ and }j\in V\setminus C\}$
$\blacksquare$

$\{\phi(j)+\tau,\phi(j):ji\in E\text{ and }j\in V\setminus C\}$

In the full version of the paper, we prove Lemma 11, which states that if $\phi(i)$ does not fall into one of the “forbidden” points for $(i,\phi,C)$ , then $\phi_{C}^{+}$ and $\phi_{C}^{-}$ have the same cost as $\phi$ .

Lemma 11.

Given a network $N$ and min $s$ - $d$ cut function $\phi$ , let $C\subseteq V\setminus X_{\phi}$ satisfy $\phi(i)\notin\texttt{forbidden}_{\phi,C}(i)$ for all $i\in C$ . Then $cost(\phi_{C}^{+})=cost(\phi_{C}^{-})=cost(\phi)$ .

Figure 1: The center of this figure depicts a min cut

\phi

in part of a TEN by denoting nodes on

(s,0)

’s side of the cut in green and nodes on the other side in red. The images on the left and right depict the same for

\phi_{C}^{-}

and

\phi_{C}^{+}

, respectively. Note that

\phi_{C}^{-}

incurs an extra cost for edge

i j

compared to

\phi

, as

(i,\phi(i)-1)

is now on

(s,0)

’s side of the cut. However,

\phi_{C}^{+}

does not incur an equivalent discount for moving

(i,\phi(i))

to the other side of the cut, because the edge leaving that node was already free under

\phi

. This is a direct result of the fact that

i\in C,j\in V\setminus C

and

\phi(i)+\tau=\phi(j)

.

We briefly outline the idea of this lemma. Note that some number of copies of each edge $ij\in E$ crosses the cut defined by $\phi$ . We want to show that if $\phi_{C}^{+}$ incurs some additional cost by having an extra copy of $i j$ cross it as compared to $\phi$ , then $\phi_{C}^{-}$ obtains an equivalent “discount” by having one less copy of $i j$ cross it as compared to $\phi$ . Conversely, $\phi_{C}^{+}$ gets a total discount equal to the total extra cost of $\phi_{C}^{-}$ . As neither $\phi_{C}^{+}$ nor $\phi_{C}^{-}$ can be cheaper than $\phi$ , it must be the case that all three cuts have the same cost. Figure 1 exhibits an example showing why the property $\phi(i)\notin\texttt{forbidden}_{i,C}(\phi)$ for all $i\in C$ is important in the statement of the lemma: if this property does not hold for some $\phi$ and $C$ , the costs and discounts described above might not offset each other.

In the full version of the paper, we use Lemma 11 to prove Lemma 8. At a high level, consider a min cut function $\phi$ that maximizes $\sum_{i\in V}\phi(i)$ . We show that if $\textsc{Range}(\phi)\cap[T]\not\subseteq\textsc{CriticalTimes}(N)$ , there exists an $i\in V$ such that $\phi(i)$ is not offset from any $\theta\in\mathcal{T}$ by a multiple of $\tau$ . We define $C$ to be $i$ and all of the nodes $j$ such that $\phi(j)$ is offset from $\phi(i)$ by a multiple of $\tau$ , and we show that $C$ meets the criteria of Lemma 11, so $\phi_{C}^{+}$ is a min cut with $\sum_{i\in V}\phi_{C}^{+}(i)\geq\sum_{i\in V}\phi(i)$ , which contradicts how we picked $\phi$ .

References

[1] E. J. Anderson, P. Nash, and A. B. Philpott. A class of continuous network flow problems. Mathematics of Operations Research, 7(4):501–514, 1982. doi:10.1287/MOOR.7.4.501.
[2] Li Chen, Rasmus Kyng, Yang P Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 612–623. IEEE, 2022. doi:10.1109/FOCS54457.2022.00064.
[3] Lester Randolph Ford and Delbert R Fulkerson. Maximal flow through a network. Canadian journal of Mathematics, 8:399–404, 1956.
[4] Bruce Hoppe and Eva Tardos. The quickest transshipment problem. Mathematics of Operations Research, 25(1):36–62, 2000. doi:10.1287/MOOR.25.1.36.15211.
[5] Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong. A faster cutting plane method and its implications for combinatorial and convex optimization. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1049–1065. IEEE, 2015. doi:10.1109/FOCS.2015.68.
[6] James B Orlin. A polynomial time primal network simplex algorithm for minimum cost flows. Mathematical Programming, 78(2):109–129, 1997. doi:10.1007/BF02614365.
[7] James B. Orlin. Max flows in o(nm) time, or better. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’13, pages 765–774, New York, NY, USA, 2013. Association for Computing Machinery. doi:10.1145/2488608.2488705.
[8] Martin Skutella. An introduction to network flows over time. In William Cook, László Lovász, and Jens Vygen, editors, Research Trends in Combinatorial Optimization: Bonn 2008, pages 451–482. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009. doi:10.1007/978-3-540-76796-1_21.

[bib.bib1] [1] E. J. Anderson, P. Nash, and A. B. Philpott. A class of continuous network flow problems. Mathematics of Operations Research, 7(4):501–514, 1982. doi:10.1287/MOOR.7.4.501.

[bib.bib2] [2] Li Chen, Rasmus Kyng, Yang P Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 612–623. IEEE, 2022. doi:10.1109/FOCS54457.2022.00064.

[bib.bib3] [3] Lester Randolph Ford and Delbert R Fulkerson. Maximal flow through a network. Canadian journal of Mathematics, 8:399–404, 1956.

[bib.bib4] [4] Bruce Hoppe and Eva Tardos. The quickest transshipment problem. Mathematics of Operations Research, 25(1):36–62, 2000. doi:10.1287/MOOR.25.1.36.15211.

[bib.bib5] [5] Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong. A faster cutting plane method and its implications for combinatorial and convex optimization. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1049–1065. IEEE, 2015. doi:10.1109/FOCS.2015.68.

[bib.bib6] [6] James B Orlin. A polynomial time primal network simplex algorithm for minimum cost flows. Mathematical Programming, 78(2):109–129, 1997. doi:10.1007/BF02614365.

[bib.bib7] [7] James B. Orlin. Max flows in o(nm) time, or better. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’13, pages 765–774, New York, NY, USA, 2013. Association for Computing Machinery. doi:10.1145/2488608.2488705.

[bib.bib8] [8] Martin Skutella. An introduction to network flows over time. In William Cook, László Lovász, and Jens Vygen, editors, Research Trends in Combinatorial Optimization: Bonn 2008, pages 451–482. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009. doi:10.1007/978-3-540-76796-1_21.