Stoer–Wagner Min Cut

Mechthild Stoer & Frank Wagner, 1994

Stoer–Wagner (1994) finds the global minimum cut by repeating a maximum-adjacency-ordering phase, recording the cut-of-the-phase, then merging the last two vertices. The best cut found across all phases is the answer.