An O(EVIog2V) algorithm for the maximal flow problem

摘要

An O(EV log2 V) algorithm for finding the maximal flow in networks is described. It is asymptotically better than the other known algorithms if E = O(V2−ϵ) for some ϵ > 0. The analysis of the running time exploits the discovery of a phenomenon similar to (but more general than) path compression, although the “union find” algorithm is not used. The time bound is shown to be tight in terms of V and E by exhibiting a family of networks that require time.1