Eleonor Ciurea, Mircea Parpalea: Shortest conditional decreasing path algorithm for the parametric minimum flow problem, p.387-401

Abstract:

This article presents a decreasing directed paths algorithm for the parametric minimum flow problem. The algorithm always finds a shortest conditional decreasing directed path from the source node to the sink node in a parametric residual network and decreases the flow along the corresponding path in the original parametric network. On each of the iterations, the shortest conditional decreasing path (SCDP) algorithm computes a sub-interval of the parameter value within a decreasing of flow is possible and the maximum amount by which the flow can be decreased. The complexity of the SCDP algorithm is $O(n^{2}m^{2}K + nm K^{2})$ where $K-1$ is the number of breakpoints of the piecewise linear minimum flow value function, $n$ and $m$ being respectively the number of nodes and the number of arcs in the network.

Key Words: Network flow, parametric minimum flow problem, decreasing paths algorithm.

2000 Mathematics Subject Classification: Primary: 90B10;
Secondary: 90C35, 90C47, 05C35, 68R10.

Download the paper in pdf format here.