Article · Español
En ciencias de la computación y teoría de grafos, el Algoritmo de Edmonds-Karp es una implementación del método de Ford-Fulkerson para calcular el flujo maximal en una red de flujo(i.e. computer network) con complejidad O(V E2). Es asintóticamente más lento que el , que tiene complejidad O(V3), pero es habitualmente más rápido en la práctica para grafos ralos. El algoritmo fue publicado por primera vez por un científico soviético, Yefim (Chaim) Dinic, en 1970, e independientemente por Jack Edmonds y Richard Karp en 1972. El Algoritmo de Dinic incluye técnicas adicionales para reducir la complejidad a O(V2E).
Abstract from DBpedia / Wikipedia · CC BY-SA