Quick links

Improved Time Bounds for the Maximum Flow Problem

Report ID:
TR-118-87
Date:
August 1987
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.

Follow us: Facebook Twitter Linkedin