Dinic's algorithm, also called Dinitz's algorithm, is a strongly polynomial algorithm for computing the maximum flow in a flow network, conceived in 1970 by the Israeli computer scientist Yefim Dinitz. Like the Edmonds-Karp algorithm, it works by repeatedly finding shortest augmenting paths, but it introduces the concepts of the level graph and blocking flow to reach a better running time. It remains one of the standard textbook algorithms for the maximum flow problem.
Facts
Time Complexity
Time Complexity (category)Polynomial Time -- O(n^k) 1 Connections
Credited To
Source Dinic's Algorithm (Wikipedia)
In Field
Source Dinic's Algorithm (Wikipedia)
Invented By
Source Dinic's Algorithm (Wikipedia)
Sources
1. Dinic's Algorithm (Wikipedia)
Wikipedia infobox: time complexity polynomial
polynomial
In Field: Algorithms and Complexity Theory, Lead sentence
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 Dinitz.
Invented By: Yefim Dinitz, Lead
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 Dinitz.
Credited To: Yefim Dinitz, Lead
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 Dinitz.
In Group: Network Flow and Matching Algorithms, Lead section
computing the maximum flow in a flow network
View the SourceWikidata: Dinic's Algorithm
Wikidata Q730933, class allow-list match (w-wdresolver-0926)View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.