Tag: probabilistic-algorithms

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