corc logo

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.