A FASTER DETERMINISTIC MAXIMUM FLOW ALGORITHM

Cheriyan and Hagerup developed a randomized algorithm to compute the maximum flow in a graph with n nodes and m edges in O(mn + n2 log2 n) 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(mn(log(m/n log n) n)). Our algorithm gives an O(mn) deterministic algorithm for all m/n = OMEGA(n(epsilon)) for any positive constant epsilon, and is currently the fastest deterministic algorithm for comuting maximum flow as long as m/n = omega(log n). (C) 1994 Academic Press, Inc.