A New Approach to the Maximum-Flow Problem

A New Approach to the Maximum-Flow Problem

October 1988 | ANDREW V. GOLDBERG AND ROBERT E. TARJAN
This paper presents a new approach to the maximum-flow problem, which is based on the preflow concept introduced by Karzanov. The algorithm maintains a preflow in the original network and pushes local flow excess toward the sink along estimated shortest paths in the residual graph. The algorithm is simple and intuitive, yet it runs as fast as any other known method on dense graphs, achieving an O(n³) time bound on an n-vertex graph. By incorporating the dynamic tree data structure of Sleator and Tarjan, the algorithm runs in O(nm log(n²/m)) time on an n-vertex, m-edge graph. This is as fast as any known method for any graph density and faster on graphs of moderate density. The algorithm also admits efficient distributed and parallel implementations. A parallel implementation running in O(n² log n) time using n processors and O(m) space is obtained. This time bound matches that of the Shiloach–Vishkin algorithm, which also uses n processors but requires O(n²) space. The algorithm is simple and intuitive, with natural implementations in sequential and parallel models of computation. It has been shown to be correct and terminate, with time bounds that match the best known results for both sparse and dense graphs. The algorithm can be generalized to solve the minimum-cost flow problem.This paper presents a new approach to the maximum-flow problem, which is based on the preflow concept introduced by Karzanov. The algorithm maintains a preflow in the original network and pushes local flow excess toward the sink along estimated shortest paths in the residual graph. The algorithm is simple and intuitive, yet it runs as fast as any other known method on dense graphs, achieving an O(n³) time bound on an n-vertex graph. By incorporating the dynamic tree data structure of Sleator and Tarjan, the algorithm runs in O(nm log(n²/m)) time on an n-vertex, m-edge graph. This is as fast as any known method for any graph density and faster on graphs of moderate density. The algorithm also admits efficient distributed and parallel implementations. A parallel implementation running in O(n² log n) time using n processors and O(m) space is obtained. This time bound matches that of the Shiloach–Vishkin algorithm, which also uses n processors but requires O(n²) space. The algorithm is simple and intuitive, with natural implementations in sequential and parallel models of computation. It has been shown to be correct and terminate, with time bounds that match the best known results for both sparse and dense graphs. The algorithm can be generalized to solve the minimum-cost flow problem.
Reach us at info@study.space
Understanding A new approach to the maximum-flow problem