A O(nm log(U/n)) time maximum flow algorithm

A O(nm log(U/n)) time maximum flow algorithm

0.00 Avg rating0 Votes
Article ID: iaor20011995
Country: United States
Volume: 47
Issue: 6
Start Page Number: 511
End Page Number: 520
Publication Date: Sep 2000
Journal: Naval Research Logistics
Authors: ,
Abstract:

In this paper, we present an O(nm log(U/n)) time maximum flow algorithm. If U = O(n) then this algorithm runs in O(nm) time for all values of m and n. This gives the best available running time to solve maximum flow problems satisfying U = O(n). Furthermore, for unit capacity networks the algorithm runs in O(n2/3m) time. It is a two-phase capacity scaling algorithm that is easy to implement and does not use complex data structures.

Reviews

Required fields are marked *. Your email address will not be published.