Home → Magazine Archive → August 2014 (Vol. 57, No. 8) → Efficient Maximum Flow Algorithms → Abstract

Efficient Maximum Flow Algorithms

By Andrew V. Goldberg, Robert E. Tarjan

Communications of the ACM, Vol. 57 No. 8, Pages 82-89

[article image]

The maximum flow problem and its dual, the minimum cut problem, are classical combinatorial optimization problems with many applications in science and engineering; see, for example, Ahuja et al.1 The problem is a special case of linear programming and can be solved using general linear programming techniques or their specializations (such as the network simplex method9). However, special-purpose algorithms are more efficient. Moreover, algorithm design techniques and data structures developed to compute maximum flows are useful for other problems as well. Although a special case of linear programming, the maximum flow problem is general enough so several important problems (such as the maximum bipartite matching problem) reduce to it.

Back to Top

Key Insights


Here, we survey basic techniques behind efficient maximum flow algorithms, starting with the history and basic ideas behind the fundamental maximum flow algorithms, then explore the algorithms in more detail. We restrict ourselves to basic maximum flow algorithms and do not cover interesting special cases (such as undirected graphs, planar graphs, and bipartite matchings) or generalizations (such as minimum-cost and multi-commodity flow problems).


No entries found