A sequential algorithm for finding the solution of the parametric minimum flow problem

This article presents a sequential approach for the parametric minimum flow problem. It consists in repeatedly applying a non parametric maximum flow algorithm in a modified network for a sequence of parameter values in an increasing order. The algorithm computes an initial minimum flow for a given fixed value of the parameter and then repeatedly finds a maximum flow by which the flow can be decreased over the next interval of the parameter values so that the maximum cut not to change. This maximum flow is computed as a maximum flow problem in a modified network with properly set lower and upper bounds. On each of the iterations, the algorithm computes a new breakpoint of the piecewise linear minimum flow value function and the corresponding parametric minimum flow.