Improved time bounds for the maximum flow problem

Recently, A.V. Goldberg proposed a new approach to the maximum network flow problem. The approach yields a very simple algorithm running in O(n³) time on n-vertex networks. Incorporation of the dynamic tree data structure of D.D. Sleator and R.E. Tarjan yields a more complicated algorithm with a running time of O(nm log (n²/m)) on m-arc networks. R.K. Ahuja and J.B. Orlin developed a variant of Goldberg's algorithm that uses scaling and runs in O(nm + n² 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² log U/log log U) is obtained by using a nonconstant scaling factor. Second, an even better bound of O(nm + n²(log U)^HLF 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)^HLF + 2)).