CMPS42A Karger mincut
C. Seshadhri · 67:28
Karger’s min-cut algorithm finds a graph’s global minimum cut by repeatedly contracting a uniformly random edge until two supernodes remain, then reporting the parallel edges between them. A single trial succeeds with...