TY - GEN

T1 - A faster deterministic maximum flow algorithm

AU - King, V.

AU - Rao, S.

AU - Tarjan, R.

PY - 1992/9/1

Y1 - 1992/9/1

N2 - We describe a deterministic version of a 1990 Cheriyan, Hagerup, and Mehlhorn randomized algorithm for computing the maximum flow on a directed graph with n nodes and m edges which runs in time O(mn + n 2+∈), for any constant ∈. This improves upon Alon's 1989 bound of O(mn + n8/3log n) [A] and gives an O(mn) deterministic algorithm for all m > n1+∈. Thus it extends the range of m/n for which an 0{mn) algorithm is known, and matches the 1988 algorithm of Goldberg and Tarjan [GT] for smaller values of m/n.

AB - We describe a deterministic version of a 1990 Cheriyan, Hagerup, and Mehlhorn randomized algorithm for computing the maximum flow on a directed graph with n nodes and m edges which runs in time O(mn + n 2+∈), for any constant ∈. This improves upon Alon's 1989 bound of O(mn + n8/3log n) [A] and gives an O(mn) deterministic algorithm for all m > n1+∈. Thus it extends the range of m/n for which an 0{mn) algorithm is known, and matches the 1988 algorithm of Goldberg and Tarjan [GT] for smaller values of m/n.

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

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

M3 - Conference contribution

AN - SCOPUS:85025242609

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 157

EP - 164

BT - Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992

PB - Association for Computing Machinery

T2 - 3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992

Y2 - 27 January 1992 through 29 January 1992

ER -