Summary: Recently, \textit{A. V. Goldberg} [A new max-flow algorithm, Tech. Rep. MIT/LCS/TM-291, Lab. Comput. Sci., Mass. Inst. Technol. (Cambridge/MA 1985)] 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 \textit{D. Sleator} and \textit{R. Tarjan} [J. Comput. Syst. Sci. 26, 362-391 (1983; Zbl 0509.68058)] yields a more complicated algorithm with a running time of O(nm log(n\({}^ 2/m))\) on m-arc networks. \textit{R. Ahuja} and \textit{J. B. Orlin} [A fast and simple algorithm for the maximum flow problem, Oper. Res. (to appear)] 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 \textit{R. Tarjan} [Oper. Res. Lett. 2, 265-286 (1984; Zbl 0542.05057)]. 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_ nU)\), which is the time needed to read the input in the model.