01
Karger and the Randomized Minimum-Cut Algorithm
David Karger's contraction algorithm showed that repeatedly choosing random edges and merging their endpoints could reveal a global minimum cut with analyzable probability.
↗
Collection
David Karger's contraction algorithm showed that repeatedly choosing random edges and merging their endpoints could reveal a global minimum cut with analyzable probability.
Randomized algorithms made probability part of the algorithm itself. Work by Michael Rabin and by Robert Solovay with Volker Strassen helped show in the 1970s that controlled error or randomized choices could buy dramatic computational savings.