Improved Time Bounds for the Maximum Flow Problem,
Abstract
A new approach is proposed to the maximum network flow problem. The approach yields a very simple algorithm running O(n-cubed) 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(nm log (n-squared/m)) on m-edge networks. A variant of the algorithm is developed that uses scaling and runs in O(nm + (n-sq) log U) time on networks with integer edge capacities bounded by U. This paper obtains a modification of the Ahuja-Orlin algorithm with a running time of O(nm + (n-sq) (log U)/(log log u). The use of dynamic trees in this algorithm further reduces the time bound on O(nm log (n log U/mlog 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1987
- Accession Number
- ADA194034
Entities
People
- James B. Orlin
- Ravindra K. Ahuma
- Robert Tarjan
Organizations
- Princeton University