A Faster Deterministic Maximum Flow Algorithm

✍ Scribed by V. King; S. Rao; R. Tarjan

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 1011 KB
• Volume: 17
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1994.1044

✦ Synopsis

Cheriyan and Hagerup developed a randomized algorithm to compute the maximum flow in a graph with (n) nodes and (m) edges in (O\left(m n+n^{2} \log ^{2} n\right)) expected time. The randomization is used to efficiently play a certain combinatorial game that arises during the computation. We give a version of their algorithm where a general version of their game arises. Then we give a strategy for the game that yields a deterministic algorithm for computing the maximum flow in a directed graph with (n) nodes and (m) edges that runs in time (O\left(m n\left(\log _{m / n \log n} n\right)\right)). Our algorithm gives an (O(m n)) deterministic algorithm for all (m / n=\Omega\left(n^{\epsilon}\right)) for any positive constant (\epsilon), and is currently the fastest deterministic algorithm for computing maximum flow as long as (m / n=\omega(\log n)). 1994 Academic Press, Inc.