Efficient maximum flow algorithms

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(n²/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.