Maximum ow over time problem in parametric networks

Abstract

The article presents the maximum parametric ow problem in discrete dynamic networks with linear capacities and zeroes lower bounds. Based on an approach of partitioning the values range of the parameter, the algorithm proposed for solving the problem finds the maximum ow for a sequence of the parameter values, in their increasing order. The flow is repeatedly augmented along the shortest paths from source to sink in the time-space network, avoiding the explicit time expansion of the network. In each of its iterations, besides the maximum ow, the algorithm also computes a new value of the parameter up to which the computed ow remains a maximum one. Finally, the complexity of the algorithm is computed.