TY - JOUR

T1 - Efficient maximum flow algorithms

AU - Goldberg, Andrew V.

AU - Tarjan, Robert E.

N1 - Copyright:
Copyright 2014 Elsevier B.V., All rights reserved.

PY - 2014/8

Y1 - 2014/8

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84905242058&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84905242058&partnerID=8YFLogxK

U2 - 10.1145/2628036

DO - 10.1145/2628036

M3 - Review article

AN - SCOPUS:84905242058

SN - 0001-0782

VL - 57

SP - 82

EP - 89

JO - Communications of the ACM

JF - Communications of the ACM

IS - 8

ER -