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 -