Improved Time Bounds for the Maximum Flow Problem
Ravindra K. Ahuja, James B. Orlin, Robert Endre Tarjan · SIAM Journal on Computing · 1989
Recently, Goldberg proposed a new approach to the maximum network flow problem. The approach yields a very simple algorithm running in $O(n^3 )$ time on n-vertex networks. Incorporation of the dynamic tree data structure of Sleator and Tarjan yields a more complicated algorithm with a running time of $O(nm\log (n^2 /m)$ on m-arc networks. Ahuja and Orlin developed a variant of Goldberg’s algorithm that uses scaling and runs in $O(nm + (n^2 \log U)$ time on networks with integer arc capacities bounded by U. In this paper possible improvements to the Ahuja-Orlin algorithm are explored. First, an improved running time of $O(nm + n^2 \log U/\log \log U)$ is obtained by using a nonconstant scaling factor. Second, an even better bound of $O(nm + n^2 (\log U)^{1/2} )$ is obtained by combining the Ahuja-Orlin algorithm with the wave algorithm of Tarjan. Third, it is shown that the use of dynamic trees in the latter algorithm reduces the running time to $O(nm\log (({n / m})(\log U)^{{1 / 2}} + 2))$. This result shows that the combined use of three different techniques, results in speed not obtained by using any of the techniques alone. The above bounds are all for a unit-cost random access machine. Also considered is a semilogarithmic computation model in which the bounds increase by an additive term of $O(m\log _n U)$, which is the time needed to read the input in the model.