|
Distance-directed algorithms for maximum flow and parametric maximum flow problems J.B. Orlin and R.K. Ahuja, Naval Research Logistics 38, 413-430, 1991 Until recently, fast algorithms for the maximum flow problem have typically proceeded by constructing layered networks and establishing blocking flows in these networks. However, in the recent years, new "distance-directed" algorithms have been suggested that do not construct layered networks but instead maintain a "distance label" with each node. The distance label of a node is a lower bound on the length of the shortest augmenting path from the node to the sink. In this paper, we develop two new distance-directed augmenting path algorithms for the maximum flow problem. Both the algorithms run in O(n2m) time. We show that these algorithms are equivalent to Edmonds-Karp and Dinic's algorithm in the sense that they enumerate the same augmenting paths in the same sequence. Using a scaling technique, we improve the complexity of our distance-directed algorithms to O(nm log U), where U denotes the largest arc capacity. We also consider applications of these algorithms to unit capacity maximum flow problems and a class of parametric maximum flow problem. |