Recursive Random Contraction Revisited
Recursive Random Contraction Revisited
In this note, we revisit the recursive random contraction algorithm of Karger and Stein [4] for finding a minimum cut in a graph. Our revisit is occasioned by a paper of Fox, Panigrahi, and Zhang [1] which gives an extension of the Karger-Stein algorithm to minimum cuts and minimum k-cuts …