Theoretical Efficiency of the Edmonds-Karp Algorithm for Computing Maximal Flows

AnSTnACT. This paper deals with the "first labelled first scanned" maximal flow algorithm proposed by Edmonds and Karp as described by Hu. It is shown that flow problems using their method may require O(n") augmentations. In particular, examples of networks with n nodes which require ,~-~n s and ~-~n s augmentations are presented. The bound derived by Edmonds and Karp is improved to min ((n ] A I - I A I ~t2 4-4n~), [n -1](I A I -n 4-2)) where n is the number of nodes and I A ] is the number of arcs. These results are translated for the newer version of their algorithm to appear in J. ACM.