Partitioning Algorithm for the Parametric Maximum Flow

摘要

The article presents an approach to the maximum flow problem in parametric networks with linear capacity functions of a single parameter, based on the concept of shortest conditional augmenting directed path. In order to avoid working with piecewise linear functions, our approach uses a series of parametric residual networks defined for successive subintervals of the parameter values where the parametric residual capacities of all arcs remain linear functions. Besides working with linear instead piecewise linear functions, another main advantage of our approach is that every directed path in such a parametric residual network is also a conditional augmenting directed path for the subinterval for which the parametric residual network was defined. The complexity of the partitioning algorithm is O (Kn2m) where K is the number of partitioning points of the parameter values interval, n and m being the number of nodes, respectively the number of arcs in the network.