Euiwoong Lee (이의웅), The Karger-Stein algorithm is optimal for k-cut
Room B232 IBS (기초과학연구원)In the k-cut problem, we are given an edge-weighted graph and want to find the least-weight set of edges whose deletion breaks the graph into k connected components. It is easy to see that the elegant randomized contraction algorithm of Karger and Stein for global mincut (k=2) can be naturally extended for general k with …