Given a graph with
, 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 vertices remaining.

**Subsections**

Ali Salehi
2005-04-29