Improved Time Bounds for the Maximum Flow Problem

Recently, Goldberg proposed a new approach lo the maximum netv.ork flow problem. The approach yields a ver> ' simple algorithm nmning in 0{n^) 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 0{rvn log {n ^ Im)) on m-arc networks. Ahuja and Orlin developed a variant of Goldberg's algorithm that uses scaling and runs in 0(,rm + n ' logL') time on net-works with integer arc capacities bounded by U. In this paper we explore possi-ble improvements to the Ahuja-Oriin algorithm. First we obtain an improved run-ning lime of 0(,nm-t- n ^ logL'/log logL') by using a nonconsiant scaling factor. Then we obtain an even better bound of 0{run-t- n^Qogt/)'^) by combining the Ahuja-Orlin algorithm with the wave algorithm of Tarjan. Fmally. we show that the use of dynamic trees in the laner algorithm reduces the running time to 0{rvn log( — Gogt/) ' ' + 2)). This result shows that the combined use of three tn different techniques results in speed not obtained by using any of the techniques alone