Recently, A.V. Goldberg proposed a new approach to the maximum network flow problem. The approach yields a very simple algorithm running in O(n3) 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 (n2/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 + n2 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 + n2 log U/log log U) is obtained by using a nonconstant scaling factor. Second, an even better bound of O(nm + n2(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)).
All Science Journal Classification (ASJC) codes
- Computer Science(all)