Content deleted Content added
Nkojuharov (talk | contribs) No edit summary |
Nkojuharov (talk | contribs) No edit summary |
||
Line 3:
The Edmonds-Karp algorithm runs in [[Big O notation|O]](VE<sup>2</sup>) time, where V is the number of vertices and E is the number of edges in the network.
The algorithm was first discovered by a Russian scientist, Dinits, in 1970, and later, independently, by Edmonds and Karp who published it in the 1972 paper "Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems," by [[Jack Edmonds]] and [[Richard Karp]], in the ''Journal of the [[Association for Computing Machinery|ACM]]''. Dinits actually proved a tighter bound on the algorithm, [[Big O notation|O]](EV<sup>2</sup>).
==External link==
| |||