Abstract of CORC technical report TR-98-03:
Universally maximum flow with piecewise constant
capacities
Lisa Fleischer, 1998
A maximum dynamic flow generalizes the standard maximum flow
problem by introducing time. The object is to send as much flow from
source to sink in T time units as possible. A related
problem is the universally maximum flow, which asks to send a
flow from source to sink that maximizes the amount of flow arriving at
the sink by time t for all
t < T. We consider a further
generalization of this problem that allows arc and node capacities to
change over time. In particular, given a network with arc and node
capacities that are piecewise constant functions of time with at most
k breakpoints, and a time bound T, we show how to
compute a flow that maximizes the amount of flow reaching the sink in
all time intervals (0, t ] for all
0 < t < T in
O(k²mn log(kn²/m)) time. The
best previous algorithm requires O(nk) maximum flow
computations on a network with (m + n) k
arcs and nk nodes.