A generalized dynamic flows problem
Jonathan Halpern · Networks · 1979
Abstract The original maximal dynamic flows problem is to find the maximal flow that may be transferred within a given period of time, from the source to the destination of a network with constant edge capacities and lengths. This paper generalizes the problem in two ways. First, the edge's capacity is time dependent, and secondly, the heldover of flows in the vertices may be prohibited during certain intervals of time. The presence of these two additional features implies that cycling of flows may be necessary in order to generate an optimal solution, an impossible result in the original problem. The generalized maximal dynamic flows problem requires, therefore, a special method of solution, and the paper presents a suitable algorithm which solves the problem.