A Fast and Simple Algorithm for the Maximum Flow Problem

R. K. Ahuja and James B. Orlin
Additional contact information
R. K. Ahuja: Massachusetts Institute of Technology, Cambridge, Massachusetts and Indian Institute of Technology, Kanpur, India
James B. Orlin: Massachusetts Institute of Technology, Cambridge, Massachusetts

Operations Research, 1989, vol. 37, issue 5, 748-759

Abstract: We present a simple sequential algorithm for the maximum flow problem on a network with n nodes, m arcs, and integer arc capacities bounded by U . Under the practical assumption that U is polynomially bounded in n , our algorithm runs in time O ( nm + n 2 log n ). This result improves the previous best bound of O ( nm log( n 2 / m )), obtained by Goldberg and Tarjan, by a factor of log n for networks that are both nonsparse and nondense without using any complex data structures. We also describe a parallel implementation of the algorithm that runs in O ( n 2 log U log p ) time in the PRAM model with EREW and uses only p processors where p = ⌈ m / n ⌉.

Keywords: networks/graphs; flow algorithms: fast and simple algorithm for the maximum flow problem (search for similar items in EconPapers)
Date: 1989
References: Add references at CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.37.5.748 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:37:y:1989:i:5:p:748-759

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().