# Dinitz’ Algorithm: The Original Version and Even’s Version

• Yefim Dinitz
Chapter
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3895)

## Abstract

This paper is devoted to the max-flow algorithm of the author: to its original version, which turned out to be unknown to non-Russian readers, and to its modification created by Shimon Even and Alon Itai; the latter became known worldwide as “Dinic’s algorithm”. It also presents the origins of the Soviet school of algorithms, which remain unknown to the Western Computer Science community, and the substantial influence of Shimon Even on the fortune of this algorithm.

## Keywords

Short Path Layered Network Outgoing Edge Incoming Edge Edge Removal
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

## References

1. 1.
Adel’son-Vel’sky, G.M., Landis, E.M.: An algorithm for the organization of information. Soviet Mathematics Doklady 3, 1259–1263 (1962)Google Scholar
2. 2.
Ford, L.R., Fulkerson, D.R.: Flows in networks. Princeton University Press, Princeton (1962)
3. 3.
Arlazarov, V.L., Dinic, E.A., Kronrod, M.A., Faradjev, I.A.: On economical finding of transitive closure of a graph. Doklady Akademii Nauk SSSR 194 (3) (1970) (in Russian); English transl.: Soviet Mathematics Doklady 11, 1270– 1272 (1970)Google Scholar
4. 4.
Dinic, E.A.: An algorithm for the solution of the max-flow problem with the polynomial estimation. Doklady Akademii Nauk SSSR 194(4) (1970) (in Russian); English transl.: Soviet Mathematics Doklady 11, 1277–1280 (1970)Google Scholar
5. 5.
Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. J. of ACM 19, 248–264 (1972)
6. 6.
Dinic, E.A.: An efficient algorithm for the solution of the generalized set representatives problem. In: Voprosy Kibernetiki, Proc. of the Seminar on Combinatorial Mathematics (Moscow, 1971) Scientific Council on the Complex Problem “Kibernetika”, Akad. Nauk SSSR, pp. 49–54 (1973) (in Russian)Google Scholar
7. 7.
Karzanov, A.V.: An exact time bound for a max-flow finding algorithm applied to the representatives’ problem. In: Voprosy Kibernetiki. Proc. of the Seminar on Combinatorial Mathematics (Moscow, 1971). Scientific Council on the Complex Problem Kibernetika, Akad. Nauk SSSR, pp.66–70 (1973) (in Russian) Google Scholar
8. 8.
Hopkroft, J., Karp, R.M.: An n5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. on Computing 2, 225–231 (1973)
9. 9.
Karzanov, A.V.: Determining the maximum flow in the network by the method of preflows. Doklady Akademii Nauk SSSR 215(1) (1974) (in Russian); English transl. Soviet Mathematics Doklady 15 , 434–437 (1974)Google Scholar
10. 10.
Adel’son-Vel’sky, G.M., Dinic, E.A., Karzanov, A.V.: Network flow algorithms. “Nauka”, Moscow, p. 119 (1975) (in Russian; a review in English see in [25]) Google Scholar
11. 11.
Even, S., Tarjan, R.E.: Network flow and testing graph connectivity. SIAM J. on Computing 4, 507–518 (1975)
12. 12.
Cherkassky, B.V.: An algorithm for building a max-flow in a network, running in time O(n2 $$\sqrt{p}$$). Mathematical Methods for Solving Economic Problems 7, 117–126 (1977) “Nauka”, Moscow, 117–126 (in Russian)Google Scholar
13. 13.
Cherkassky, B.V.: A fast algorithm for constructing a maximum flow through a network. In Combinatorial Methods in Network Flow Problems. VNIISI, Moscow, 90–96 (1979) (in Russian; English transl.: Amer. Math. Soc. Transl. 158(2), 23–30 (1994)Google Scholar
14. 14.
Even, S.: Graph Algorithms. Computer Science Press, Rockville (1979)
15. 15.
Galil, Z.: An O(V5/3 E2/3) algorithm for the maximal flow problem. Acta Inf. 14, 221-242 (1980)Google Scholar
16. 16.
Galil, Z., Naaman, A.: An O(EV log2V ) algorithm for the maximal flow problem. J. Comput. Syst. Sci. 21(2), 203–217 (1980)
17. 17.
Galil, Z.: On the theoretical efficiency of various network flow algorithms. Theor. Comp. Sci. 14, 103–111 (1981)
18. 18.
Shiloach, Y., Vishkin, U.: An O(n2 log n) parallel max-flow algorithm. J. of Algorithms 3, 128–146 (1982)
19. 19.
Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 24, 362–391 (1983)
20. 20.
Goldberg, A.V.: A new max-flow algorithm. TR MIT/LCS/TM-291, Laboratory for Comp. Sci., MIT, Cambridge (1985)Google Scholar
21. 21.
Tarjan, R.E.: Amortized computational complexity. SIAM J. Alg. Disc. Meth. 6(2), 306–318 (1985)
22. 22.
Goldberg, A.V., Tarjan, R.E.: A new approach to the maximum flow problem. In: Proc. of the 18th ACM Symp. on the Theory of Computing, pp. 136–146 (1986); Full paper in J. of ACM 35, 921–940 (1988)Google Scholar
23. 23.
Cormen, T., Leiserson, C., Rivest, R.: Introduction to Algorithms. McGraw-Hill, New York (1990)
24. 24.
Goldberg, A.V., Tarjan, R.E.: Finding minimum-cost circulations by successive approximation. Mathematics of Operations Research 15(3), 430–466 (1990)
25. 25.
Goldberg, A.V., Gusfield, D.: Book Review: Flow algorithms by G.M. Adel’son- Vel’sky, E.A. Dinits, and A.V. Karzanov. SIAM Reviews 33(2), 306–314 (1991)
26. 26.
Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Upper Saddle River (1993)Google Scholar
27. 27.
Cherkassky, B.V., Goldberg, A.V.: On implementing the push-relabel method for the maximum flow problem. Algorithmica 19, 390–410 (1997)
28. 28.
Goldberg, A.V.: Recent developments in maximum flow algorithms (invited lecture). In: Arnborg, S. (ed.) SWAT 1998. LNCS, vol. 1432, pp. 1–10. Springer, Heidelberg (1998)
29. 29.
Goldberg, A.V., Rao, S.: Beyond the flow decomposition barrier. Journal of ACM 45, 753–782 (1998)