Improved Time Bounds for the Maximum Flow Problem

Recently, 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 djTiamic tree data structure of Sleator and Tarjan yields a more complicated algorithm with a running time of 0(rmi log {n} Im)) on m-edge networks. Ahuja and Orlin developed a variant of Goldberg's algorithm that uses scaling and runs in 0{nm + n? logC/) time on net-works with integer edge capacities bounded by U. In this paper we obtain a modification of the Ahuja-Orlin algorithm with a running time of 7 lo"C/ 0{ntn + n). We show that the use of dvnamic trees in this algorithm loglogt/ reduces the time bound to 0{,nm log ( ^ + 2)). This result demonstrates m loglogf/ that the combined use of scaling and dynamic trees results in speed not obtained by using either technique alone