Content deleted Content added
ClueBot NG (talk | contribs) m Reverting possible vandalism by 155.33.91.216 to version by David Eppstein. Report False Positive? Thanks, ClueBot NG. (4078603) (Bot) |
m Capitalising short description "algorithm to compute the maximum flow in a flow network (equivalently; the minimum cut)" per WP:SDFORMAT (via Bandersnatch) |
||
Line 1:
{{Short description|
{{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(|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 |pages=1277–1280 |publisher=Doklady |year=1970 }}</ref><ref name=ipv>{{cite book | author = Yefim Dinitz | editor = [[Oded Goldreich]] |editor2=Arnold L. Rosenberg |editor3=Alan L. Selman |editor3-link = Alan Selman| title = Theoretical Computer Science: Essays in Memory of [[Shimon Even]] | chapter = Dinitz' Algorithm: The Original Version and Even's Version | year = 2006 | publisher = Springer | isbn = 978-3-540-32880-3 | pages = 218–240 | chapter-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 |s2cid=6375478 }}</ref> [[Dinic's algorithm]] includes additional techniques that reduce the running time to <math>O(|V|^2|E|)</math>.<ref name=ipv />{{Wikibooks|Algorithm implementation|Graphs/Maximum flow/Edmonds-Karp|Edmonds-Karp}}
| |||