Randomized min cut
Kent Quanrud · 74:54
Karger’s randomized contraction algorithm finds a global min-cut of an undirected graph by repeatedly contracting random edges (equivalently, taking the last MST edge under random weights) and succeeds with probabilit...