maxflow mincut

[am]

Progress in network flow algorithms


adapted from
H.S.Wilf, "Algorithms and Complexity" (1ed, 1994)

Author(s) Year Complexity
(V - vertices, E - edges)
Ford; Fulkerson 1956 −−−
Edmonds; Karp 1969 O(E2V )
Dinic 1970 O(EV2)
Karzanov 1973 O(V3)
Cherkassky 1976 O(sqrt(E)V2 )
Malhotra; et al : 1978 O(V3)
Galil 1978 O(V5/3E2/3)
Galil and Naamad 1979 O(EV log2V )
Sleator and Tarjan 1980 O(EV log V )
Goldberg and Tarjan 1985 O(EV log (V2/E))

Zvi Galil, Amnon Naamad, "Network flow and generalized path compression",
Annual ACM Symposium on Theory of Computing
Proceedings of the eleventh annual ACM symposium on Theory of computing
Atlanta, Georgia, United States, Pp. 13 - 26, 1979
http://portal.acm.org/citation.cfm?id=804394
Z. Galil, "A new algorithm for the maximal flow problem", Proc. 19th IEEE
http://portal.acm.org/results.cfm?query=author%3AP310584&querydisp=author%3AZvi%20%20Galil&coll=GUIDE&dl=GUIDE&CFID=27262936&CFTOKEN=56456946
Symposium on the Foundations of Computer Science, Ann Arbor, October 1978, 231-245.
Andrew V. Goldberg and Robert E. Tarjan, "A new approach to the maximum flow problem", 1985.
http://portal.acm.org/citation.cfm?id=61051
http://portal.acm.org/citation.cfm?id=12144

Next big step:

A.V. Goldberg, S. Rao
"Beyond the flow decomposition barrier"
J. ACM, 45(5):783-797, 1998.

Next, see here.