Improved Version of Randomized Min Cut:Faster Min Cut

Randomized Min Cut Algorithm finds min cut with probability $\Omega$( $\displaystyle\frac{1}{n^2}$) for the two terminal case, where n is the number of vertices. In order to find the min-cut, we have to run it for $n^2$ times. [6] There is an improved version of this algorithm, Faster Min Cut, which achieves to find a min-cut with probability $\Omega$ ( $\displaystyle\frac{1}{log\ n}$)

In Faster Min Cut, first contraction is used to form two subgraphs that has $\displaystyle\frac{n}{\sqrt{2}}$ vertices. Then recursively, min-cuts of these two subgraphs are calculated. Finally, the smaller of the min cuts of these subgraphs is chosen as the final min cut value. This algorithm can be viewed as binary computation tree. In faster min cut, the depth of tree is $log\ n$ and in the earlier version it is 1. If we had more time, we would also implement this version of randomized min cut that runs in O($n^2$logn) time and uses O($n^2$) space[6].


Ali Salehi 2005-04-29