George Giakkoupis

A fundamental result by Karger (1994) states that for any k-edge connected graph with n nodes, independently sampling each edge with probability p = Omega(logn / k) results in a graph that has edge connectivity Omega(kp), with high probability. We...