October 1988 | ANDREW V. GOLDBERG AND ROBERT E. TARJAN
The paper introduces a new approach to the maximum-flow problem, based on Karzanov's concept of a preflow. A preflow is similar to a flow but allows the total amount flowing into a vertex to exceed the total amount flowing out. The algorithm maintains a preflow in the original network and pushes local flow excess toward the sink along estimated shortest paths. This method is simple and intuitive, and it achieves an $O(n^2)$ 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^2/m))$ time on an $n$-vertex, $m$-edge graph, matching the best known bounds for both sparse and dense graphs. The algorithm also admits efficient distributed and parallel implementations, with a parallel version running in $O(n^2 \log n)$ time using $n$ processors and $O(m)$ space, matching the Shiloach-Vishkin algorithm but with improved space efficiency.The paper introduces a new approach to the maximum-flow problem, based on Karzanov's concept of a preflow. A preflow is similar to a flow but allows the total amount flowing into a vertex to exceed the total amount flowing out. The algorithm maintains a preflow in the original network and pushes local flow excess toward the sink along estimated shortest paths. This method is simple and intuitive, and it achieves an $O(n^2)$ 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^2/m))$ time on an $n$-vertex, $m$-edge graph, matching the best known bounds for both sparse and dense graphs. The algorithm also admits efficient distributed and parallel implementations, with a parallel version running in $O(n^2 \log n)$ time using $n$ processors and $O(m)$ space, matching the Shiloach-Vishkin algorithm but with improved space efficiency.