The Edmonds-Karp algorithm is an implementation of the Ford-Fulkerson method for computing the maximum flow in a flow network, distinguished from a generic Ford-Fulkerson implementation by always choosing the shortest augmenting path, measured by number of edges, using breadth-first search. The algorithm was first published by Yefim Dinitz in 1970, then independently published by Jack Edmonds and Richard Karp in 1972, whose names it carries. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
Time Complexity Credited ToYefim Dinitz, 1970 (first publication); Jack Edmonds and Richard Karp, 1972 (independent publication). 1 Connections
Invented By
Richard Karp co-developed this implementation of the Ford-Fulkerson method for computing maximum flow with Jack Edmonds, published in 1972.
Source Wikipedia: Richard M. Karp
Sources
1. Wikipedia: Edmonds-Karp Algorithm
Wikimedia FoundationLead section
In computer science, the Edmonds-Karp algorithm is an implementation of the Ford-Fulkerson method for computing the maximum flow in a flow network in O(|V||E|^2) time.
Body, history
The algorithm was first published by Yefim Dinitz in 1970, then independently published by Jack Edmonds and Richard Karp in 1972.
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.