Edmonds–Karp algorithm: Difference between revisions

Revision as of 06:35, 3 August 2006

Revision as of 06:56, 3 August 2006

Line 1:

In [[computer science]] and [[graph theory]], 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 <math>O(VE^2)</math>. It is asymptotically slower than the [[relabel-to-front algorithm]], which runs in <math>O(V^3)</math>, but it is often faster in practice for [[sparse graph]]s. The algorithm was first published by a Russian scientist, Dinic, in 1970{{ref|Din70}}, and later, independently, by [[Jack Edmonds]] and [[Richard Karp]] in 1972{{ref|EK72}} (discovered earlier). Dinic's algorithm includes additional techniques that reduce the running time to <math>O(V^2 E)</math>.

==Algorithm==