## 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(n^{2}/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 language | English (US) |
---|---|

Pages (from-to) | 82-89 |

Number of pages | 8 |

Journal | Communications of the ACM |

Volume | 57 |

Issue number | 8 |

DOIs | |

State | Published - Aug 2014 |

## All Science Journal Classification (ASJC) codes

- Computer Science(all)