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 least $1-2^{-\sqrt {nm}}$. The algorithm is always correct, and in the worst case runs in $O(nm \log n)$ time. The only use of randomi... View More