A RANDOMIZED MAXIMUM-FLOW ALGORITHM

A randomized algorithm for computing a maximum flow is presented. For an n-vertex m-edge network, the running time is O (nm + n(2)(log n)(2)) with probability at]east 1 - 2(-)root nm. The algorithm is always correct, and in the worst case runs in O(nm log n) time. The only use of randomization is to randomly permute the adjacency lists of the network vertices at the start of the execution. The analysis introduces the notion of premature target relabeling (PTR) events and shows that each PTR event contributes O (log n) amortized time to the overall running rime. The number of PTR events is always O (nm); however, it is shown that when the adjacency lists are randomly permuted, then this quantity is O (n(3)/(2)m(1/2) + n(2) log n) with high probability.