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
The paper introduces a new approach to the maximum-flow problem, based on the concept of a preflow, which is similar to a flow but allows the total amount flowing into a vertex to exceed the total amount flowing out. The method maintains a preflow in the original network and pushes local flow excess toward the sink along estimated shortest paths. The algorithm is simple and intuitive, and it runs as fast as other known methods on dense graphs, achieving an $O(n^2)$ time bound on an $n$-vertex graph. By incorporating the dynamic tree data structure, the algorithm achieves an $O(nm \log(n^2/m))$ time bound on an $n$-vertex, $m$-edge graph, which is as fast as any known method for any graph density. 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 time bound of the Shiloach–Vishkin algorithm but with improved space efficiency.The paper introduces a new approach to the maximum-flow problem, based on the concept of a preflow, which is similar to a flow but allows the total amount flowing into a vertex to exceed the total amount flowing out. The method maintains a preflow in the original network and pushes local flow excess toward the sink along estimated shortest paths. The algorithm is simple and intuitive, and it runs as fast as other known methods on dense graphs, achieving an $O(n^2)$ time bound on an $n$-vertex graph. By incorporating the dynamic tree data structure, the algorithm achieves an $O(nm \log(n^2/m))$ time bound on an $n$-vertex, $m$-edge graph, which is as fast as any known method for any graph density. 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 time bound of the Shiloach–Vishkin algorithm but with improved space efficiency.
Reach us at info@study.space