A Fast and Simple Algorithm for the Maximum Flow Problem
Operations ResearchPublished 1 October 1989Open access
Ravindra K. Ahuja, James B. Orlin
Citations148
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This work presents a simple sequential algorithm for the maximum flow problem on a network with n nodes, m arcs, and integer arc capacities bounded by U and describes a parallel implementation that runs in On2 log U log p time in the PRAM model with EREW and uses only p processors.
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
Computer Science
The Design and Analysis of Computer Algorithms
9,456 Citations1974Alfred V. Aho, John E. Hopcroft
This text introduces the basic data structures and programming techniques often used in efficient algorithms, and covers use of lists, push-down stacks, queues, trees, and graphs.
Flows in networks
4,080 Citations1962D. R. Ford, D. R. Fulkerson
Journal of the ACMTheoretical Improvements in Algorithmic Efficiency for Network Flow Problems
2,522 Citations1972Jack Edmonds, Richard M. Karp
Upper bounds on the number of steps in these algorithms are derived, and are shown to improve on the upper bounds of earlier algorithms.
Journal of the ACMA new approach to the maximum-flow problem
1,877 Citations1988Andrew V. Goldberg, Robert E. Tarjan
An alternative method based on the preflow concept of Karzanov, which runs as fast as any other known method on dense graphs, achieving an O(n) time bound on an n-vertex graph and faster on graphs of moderate density.
Birkhäuser Boston eBooksMaximal Flow Through a Network
1,856 Citations2009L. R. Ford, D. R. Fulkerson
Journal of Computer and System SciencesA data structure for dynamic trees
1,040 Citations1983Daniel D. Sleator, Robert E. Tarjan
Journal of Computer and System SciencesTime bounded random access machines
317 Citations1973Stephen Cook, Robert A. Reckhow
Journal of AlgorithmsAn O(n2log n) parallel max-flow algorithm
226 Citations1982Yossi Shiloach, Uzi Vishkin
A synchronized parallel algorithm for finding maximum flow in a directed flow network is presented, whose depth is O( n 3 ( log n) p) where p (p ≤ n) is the number of processors used.
Information Processing LettersAn O(|V|3) algorithm for finding maximum flows in networks
218 Citations1978Vishv Malhotra, Mohit Kumar +1 more
An O(V cubed) algorithm is given for finding maximum flow in capacitated networks and is being posted here to make it accessible to all in electronic form.
Solving minimum-cost flow problems by successive approximation
213 Citations1987Andrew Goldberg, Robert E. Tarjan
This work introduces a framework for solving minimum-cost flow problems and shows how to extend techniques developed for the maximum flow problem to improve the quality of a solution.
Journal of Computer and System SciencesScaling algorithms for network problems
200 Citations1985Harold N. Garbow
Princeton University Press eBooks12. On the Max-Flow Min-Cut Theorem of Networks
170 Citations1957George B. Dantzig, D. R. Fulkerson
SIAM Journal on ComputingImproved Time Bounds for the Maximum Flow Problem
140 Citations1989Ravindra K. Ahuja, James B. Orlin +1 more
Possible improvements to the Ahuja-Orlin algorithm are explored and it is shown that the use of dynamic trees in the latter algorithm reduces the running time to $O(nm\log (({n / m})(\log U)^{{1 / 2}} + 2))$.
DSpace@MIT (Massachusetts Institute of Technology)EFFICIENT GRAPH ALGORITHMS FOR SEQUENTIAL AND PARALLEL COMPUTERS
121 Citations1987Andrew V. Goldberg
This thesis proves lower bounds on the parallel complexity of the maximal independent set problem and the problem of 2-coloring a rooted tree, and introduces a frame work that allows the generalization of the maximum flow techniques to the minimum-cost flow problem.
IEEE Transactions on ComputersBinary Trees and Parallel Scheduling Algorithms
75 Citations1983Dekel, Sahni
The success in using binary trees for parallel computations, indicates that the binary tree is an important and useful design tool for parallel algorithms.
Journal of Computer and System SciencesAn O(EVIog2V) algorithm for the maximal flow problem
63 Citations1980Zvi Galil, Amnon Naamad
An O(EV log2 V) algorithm for finding the maximal flow in networks is described, which is asymptotically better than the other known algorithms if E = O(V2−ϵ) for some ϵ > 0.1.
Operations Research LettersA simple version of Karzanov's blocking flow algorithm
61 Citations1984Robert E. Tarjan
This paper proposes a simplification of Karzanov's algorithm that is easier to implement than Malhotra, Kumar and Maheshwari's method.
SIAM Journal on ComputingFast Algorithms for Bipartite Network Flow
58 Citations1987Dan Gusfield, Charles U. Martel +1 more
The results on bipartite flow are used to obtain the fastest known bounds on several combinatorial problems, and mention several additional problems involving bipartites flow where $|S|$ is much smaller than $|T|$.
Distributed relaxation methods for linear network flow problems
49 Citations1986Dimitri P. Bertsekas
A dual problem which is unconstrained, piecewise linear, and involves a dual variable for each node is formulated, and a dual algorithm that resembles a Gauss-Seidel relaxation method is proposed.
Acta InformaticaAn O(V 5/3 E 2/3) algorithm for the maximal flow problem
43 Citations1980Zvi Galil
A new algorithm for finding a maximal flow in a given network is presented that runs in time O(V5/3E2/3), where V and E are the number of the vertices and edges in the network.
Annals of Operations ResearchParallel computing in combinatorial optimization
35 Citations1988G.A.P. Kindervater, Jan Karel Lenstra
This is a review of the literature on parallel computers and algorithms relevant for combinatorial optimization by describing theoretical as well as realistic machine models for parallel computations and illustrating the resulting concepts by presenting a number of polylog parallel algorithms and P-completeness results.
RePEc: Research Papers in EconomicsNew distance-directed algorithms for maximum flow and parametric maximum flow problems
14 Citations1987James B. Orlin, Ravindra K. Ahuja
Lecture notes in computer scienceAnalysis of preflow push algorithms for maximum network flow
9 Citations1988Joseph Cheriyan, Sachin Maheshwari
An O($n\cdot I \log^2 I$) maximum-flow algorithm
4 Citations1978Yossi Shiloach
A new algorithm to find a maximum flow in a flow-network which has n vertices and m edges in time of O($n\cdot I \log^2 I$), where I = M+n is the input size (up to a constant factor) and this result improves the previous upper bound of Z.