Improved Time Bounds for the Maximum Flow Problem
Report ID: TR-118-87Author: Ahuja, Ravindra K. / Orlin, James B. / Tarjan, Robert E.
Date: 1987-09-00
Pages: 21
Download Formats: |PDF|
Abstract:
Recently, 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 Sleator and Tarjan yields a more complicated algorithm with a running time of O(nmlog(n2/m)) on m-edge networks. Ahuja and Orlin developed a variant of Goldberg's algorithm that uses scaling and runs in O(nm + n2 log U) time on networks with integer edge capacities bounded by U. In this paper we obtain a modification of the Ahuja-Orlin algorithm with a running time of O(nm+n2 {log U/log log U}). We show that the use of dynamic trees in this algorithm reduces the time bound to O(nmlog( {n log U/m log log U}+2). This result demonstrates that the combined use of scaling and dynamic trees results in speed not obtained by using either technique alone.