Advertisement

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.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

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)zbMATHGoogle Scholar
  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)zbMATHCrossRefGoogle Scholar
  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)CrossRefGoogle Scholar
  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)zbMATHCrossRefMathSciNetGoogle Scholar
  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)zbMATHGoogle Scholar
  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)zbMATHCrossRefGoogle Scholar
  17. 17.
    Galil, Z.: On the theoretical efficiency of various network flow algorithms. Theor. Comp. Sci. 14, 103–111 (1981)zbMATHCrossRefMathSciNetGoogle Scholar
  18. 18.
    Shiloach, Y., Vishkin, U.: An O(n2 log n) parallel max-flow algorithm. J. of Algorithms 3, 128–146 (1982)zbMATHCrossRefMathSciNetGoogle Scholar
  19. 19.
    Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 24, 362–391 (1983)CrossRefMathSciNetGoogle Scholar
  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)zbMATHCrossRefMathSciNetGoogle Scholar
  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)zbMATHGoogle Scholar
  24. 24.
    Goldberg, A.V., Tarjan, R.E.: Finding minimum-cost circulations by successive approximation. Mathematics of Operations Research 15(3), 430–466 (1990)zbMATHCrossRefMathSciNetGoogle Scholar
  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)CrossRefGoogle Scholar
  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)zbMATHCrossRefMathSciNetGoogle Scholar
  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)CrossRefGoogle Scholar
  29. 29.
    Goldberg, A.V., Rao, S.: Beyond the flow decomposition barrier. Journal of ACM 45, 753–782 (1998)CrossRefMathSciNetGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Yefim Dinitz
    • 1
  1. 1.Dept. of Computer ScienceBen-Gurion University of the NegevBeer-ShevaIsrael

Personalised recommendations