Efficient maximum flow algorithms

Andrew V. Goldberg, Robert E. Tarjan

Research output: Contribution to journalReview articlepeer-review

47 Scopus citations

Abstract

Some of the basic techniques behind efficient maximum flow algorithms are studied. A 2013 algorithm of Orlin achieves a strongly polynomial bound for the maximum flow problem, as well as an O(n2/log n)bound for m = O(n). This result is quite sophisticated and uses a combination of ideas from maximum flow, minimum cost flow, and dynamic connectivity algorithms. Orlin uses the binary blocking flow algorithm as a subroutine. The flow balancing algorithm starts with some initial flow, dummy excesses of plus infinity and minus infinity, and repeats arc-balancing steps until all such steps move a sufficiently small amount of flow, then rounds the flow to obtain an exact maximum flow. Another approach that yields a fast practical algorithm for maximum flow problems in computer-vision applications is that of Boykov and Kolmogorov, improving the basic augmenting path method by using bidirectional search to find augmenting paths, in combination with a clever method for retaining information from previous searches to speed up future ones.

Original languageEnglish (US)
Pages (from-to)82-89
Number of pages8
JournalCommunications of the ACM
Volume57
Issue number8
DOIs
StatePublished - Aug 2014

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Efficient maximum flow algorithms'. Together they form a unique fingerprint.

Cite this