Randomized minimum cut (Randomized algorithms, Fall 2022, Lecture 4)
Kent Quanrud · 75:19
Karger’s contraction algorithm finds a global min-cut in an undirected graph by randomly contracting edges until two supernodes remain; a single run succeeds with probability about \(1/\binom{n}{2}\), which also prove...