出典:Wikipedia
出典:『Wikipedia』 (2011/06/30 20:53 UTC 版)
In computer science and graph theory, the Edmonds–Karp algorithm is an implementation of the Ford–Fulkerson method for computing the maximum flow in a flow network in
. It is asymptotically slower than the relabel-to-front algorithm, which runs in
, but it is often faster in practice for sparse graphs. The algorithm was first published by a Russian scientist, Yefim (Chaim) Dinic, in 1970, and independently by Jack Edmonds and Richard Karp in 1972 (discovered earlier). Dinic's algorithm includes additional techniques that reduce the running time to
.