Dinic's algorithm
Dinic's algorithm or Dinitz's algorithm is a strongly polynomial algorithm for computing the maximum flow in a flow network, conceived in 1970 by Israeli (formerly Soviet) computer scientist Yefim (Chaim) A. Dinitz. The algorithm runs in time and is similar to the Edmonds–Karp algorithm, which runs in time, in that it uses shortest augmenting paths. The introduction of the concepts of the level graph and blocking flow enable Dinic's algorithm to achieve its performance.
- Comment
- enDinic's algorithm or Dinitz's algorithm is a strongly polynomial algorithm for computing the maximum flow in a flow network, conceived in 1970 by Israeli (formerly Soviet) computer scientist Yefim (Chaim) A. Dinitz. The algorithm runs in time and is similar to the Edmonds–Karp algorithm, which runs in time, in that it uses shortest augmenting paths. The introduction of the concepts of the level graph and blocking flow enable Dinic's algorithm to achieve its performance.
- Depiction
- Has abstract
- enDinic's algorithm or Dinitz's algorithm is a strongly polynomial algorithm for computing the maximum flow in a flow network, conceived in 1970 by Israeli (formerly Soviet) computer scientist Yefim (Chaim) A. Dinitz. The algorithm runs in time and is similar to the Edmonds–Karp algorithm, which runs in time, in that it uses shortest augmenting paths. The introduction of the concepts of the level graph and blocking flow enable Dinic's algorithm to achieve its performance.
- Is primary topic of
- Dinic's algorithm
- Label
- enDinic's algorithm
- Link from a Wikipage to an external page
- www.cs.bgu.ac.il/~dinitz/Papers/Dinitz_alg.pdf
- Link from a Wikipage to another Wikipage
- Alexander V. Karzanov
- Bipartite matching
- Breadth-first search
- Category:Graph algorithms
- Category:Network flow problem
- Depth-first search
- Dynamic trees
- Edmonds–Karp algorithm
- File:Dinic algorithm G1.svg
- File:Dinic algorithm G2.svg
- File:Dinic algorithm G3.svg
- File:Dinic algorithm Gf1.svg
- File:Dinic algorithm Gf2.svg
- File:Dinic algorithm Gf3.svg
- File:Dinic algorithm GL1.svg
- File:Dinic algorithm GL2.svg
- File:Dinic algorithm GL3.svg
- Flow network
- Ford–Fulkerson algorithm
- Georgy Adelson-Velsky
- Hopcroft–Karp algorithm
- Maximum flow
- Maximum flow problem
- Shimon Even
- Strongly polynomial
- Technion – Israel Institute of Technology
- SameAs
- 4tWip
- Algorithme de Dinic
- Algorithmus von Dinic
- Algoritmo de Dinic
- Algorytm Dynica
- Dinic's algorithm
- Dinicův algoritmus
- m.06zpk1k
- Q730933
- Thuật toán Dinitz
- Алгоритм Диница
- Алгоритм Дініца
- Диницов алгоритам
- الگوریتم دینیک
- ขั้นตอนวิธีของดีนิซ
- 迪尼茨算法
- Subject
- Category:Graph algorithms
- Category:Network flow problem
- Thumbnail
- WasDerivedFrom
- Dinic's algorithm?oldid=1119884267&ns=0
- WikiPageLength
- 10875
- Wikipage page ID
- 23635821
- Wikipage revision ID
- 1119884267
- WikiPageUsesTemplate
- Template:Cite book
- Template:Optimization algorithms
- Template:Reflist
- Template:Sfn
