Network flow and generalized path compression
- 1 January 1979
- proceedings article
- Published by Association for Computing Machinery (ACM)
Abstract
An O(EVlog2V) algorithm for finding the maximal flow in networks is described. It is asymptotically better than the other known algorithms if E &equil; O(V2−&egr;) for some &egr;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 &Ohgr;(EVlog2V) time.++This publication has 0 references indexed in Scilit: