Karger's Algorithm

Karger's algorithm is a randomized algorithm for computing a minimum cut of a connected graph, invented by David Karger and first published in 1993. It works by repeatedly contracting randomly chosen edges of the graph until only two vertices remain, with the edges between them forming a candidate cut; running the process many times and keeping the smallest cut found gives a high probability of finding the true minimum cut. Its simplicity and its role in establishing randomized contraction as a graph algorithm technique make it a standard example in the study of randomized algorithms.