Abstract of CORC technical report TR-98-03:

Lisa Fleischer, 1998

Amaximum dynamic flowgeneralizes the standard maximum flow problem by introducing time. The object is to send as much flow from source to sink inTtime units as possible. A related problem is theuniversally maximum flow, which asks to send a flow from source to sink that maximizes the amount of flow arriving at the sink by timetfor allt<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 mostkbreakpoints, and a time boundT, 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<TinO(k²mnlog(kn²/m)) time. The best previous algorithm requiresO(nk) maximum flow computations on a network with (m+n)karcs andnknodes.