Content deleted Content added
→top: Reduce confusion by indicating alternative transliteration of Dinitz's name |
|||
Line 1:
{{Use American English|date = April 2019}}
{{Short description|algorithm to compute the maximum flow in a flow network (equivalently; the minimum cut)}}
In [[computer science]], the '''Edmonds–Karp algorithm''' is an implementation of the [[Ford–Fulkerson algorithm|Ford–Fulkerson method]] for computing the [[maximum flow problem|maximum flow]] in a [[flow network]] in [[big O notation|<math>O</math>]]<math>(|V||E|^2)</math> time. The algorithm was first published by Yefim Dinitz (whose name is also transliterated "E. A. Dinic", notably as author of his early papers) in 1970<ref>{{cite journal |first=E. A. |last=Dinic |title=Algorithm for solution of a problem of maximum flow in a network with power estimation |journal=Soviet Mathematics - Doklady |volume=11 |issue= |pages=1277–1280 |publisher=Doklady |year=1970 |url= |doi= |id= |accessdate= }}</ref><ref>{{cite journal | author=Yefim Dinitz | title=Dinitz's Algorithm: The Original Version and Even's Version | url=http://www.cs.bgu.ac.il/~dinitz/Papers/Dinitz_alg.pdf}}</ref> and independently published by [[Jack Edmonds]] and [[Richard Karp]] in 1972.<ref>{{cite journal |last1=Edmonds |first1=Jack |author1-link=Jack Edmonds |last2=Karp |first2=Richard M. |author2-link=Richard Karp |title=Theoretical improvements in algorithmic efficiency for network flow problems |journal=Journal of the ACM |volume=19 |issue=2 |pages=248–264 |year=1972 |url=http://www.eecs.umich.edu/%7Epettie/matching/Edmonds-Karp-network-flow.pdf |doi=10.1145/321694.321699 |id= |accessdate= }}</ref> [[Dinic's algorithm]] includes additional techniques that reduce the running time to <math>O(|V|^2|E|)</math>.
==Algorithm==
| |||