The Randomized Min-Cut Algorithm

Given a graph $G(V,E)$ with $\vert V\vert = n$, our aim is to partition the graph into t partitions such that the total number of edges across partitions is minimum. The Randomized Min-Cut Algorithm iterates by choosing an edge at random from the edges of the graph and with the probability of an edge being chosen proportional to the weight of the edge. It then contracts the vertices of the chosen edge to one vertex. The algorithm terminates, when there are only $t$ vertices remaining.


Ali Salehi 2005-04-29