Edmonds and Karp's algorithm

This article covers the Edmonds-Karp algorithm. It is not to be confused with Edmonds' matching algorithm .

In computer science and graph theory, the Edmonds-Karp algorithm is an implementation of the Ford-Fulkerson method for calculating the maximum st-flow in networks with positive real capacities. It uses the shortest augmenting path in each step, which ensures that the algorithm terminates in polynomial time .

In most implementations, the shortest path is found by breadth-first search , resulting in a run time in . The algorithm was first published in 1970 by the Russian scientist EA Dinic and was later discovered independently by Jack Edmonds and Richard M. Karp , who published it in 1972. Dinics algorithm includes additional techniques to reduce the running time . ${\displaystyle {\mathcal {O}}(|V|\cdot |E|^{2})}$ ${\displaystyle {\mathcal {O}}(|V|^{2}\cdot |E|)}$

literature

• Thomas H. Cormen, Charles E. Leiserson , Ronald L. Rivest , Clifford Stein: Introduction to Algorithms, Second Edition . MIT Press and McGraw-Hill, 2001, ISBN 0-262-03293-7 , subsection 26.2: The Ford-Fulkerson method , pp. 651-664.
• Bernhard Korte , Jens Vygen : Combinatorial Optimization . Springer Berlin Heidelberg, 2012, ISBN 978-3-642-25400-0 , subsection 8.3: The Edmonds-Karp Algorithm , pp. 195–196.

Individual evidence

1. ^ Jack Edmonds , Richard M. Karp : Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems . In: J. ACM . tape 19 , no. 2 , 1972, p. 248-264 , doi : 10.1145 / 321694.321699 .
2. ↑ Santanu Saha Ray: Graph Theory with Algorithms and its Applications . 1st edition. Springer India, New Delhi, et al. 2013, ISBN 978-81-322-0749-8 , pp. 167-175 .