Tag: graph-contraction

David Karger's contraction algorithm showed that repeatedly choosing random edges and merging their endpoints could reveal a global minimum cut with analyzable probability.