Premium
A O ( nm log( U / n )) time maximum flow algorithm
Author(s) -
SedeñoNoda Antonio,
GonzálezMartín Carlos
Publication year - 2000
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(200009)47:6<511::aid-nav4>3.0.co;2-s
Subject(s) - maximum flow problem , running time , flow (mathematics) , algorithm , computer science , binary logarithm , time complexity , mathematics , mathematical optimization , combinatorics , geometry
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 ( n 2/3 m ) time. It is a two‐phase capacity scaling algorithm that is easy to implement and does not use complex data structures. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 511–520, 2000