Edmonds–Karp algorithm: Difference between revisions

Revision as of 19:00, 24 December 2020

Revision as of 08:30, 1 February 2021

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(|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 | 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 />

==Algorithm==