We provide a simple new randomized contraction approach to the global minimum
cut problem for simple undirected graphs. The contractions exploit 2-out edge
sampling from each vertex rather than the standard uniform edge sampling. We
demonstrate the power of our new approach by obtainin
该论文研究无向带权图中的最小割问题，并给出了一种用于寻找 2 - 保留（切断图 G 中两个边）图的生成树 T 的最小割的简单算法。该算法被运用在代替 Karger 的近线性时间最小割算法中的复杂子例程，采用自包含版本的 Karger 算法的新程序，其易于说明和实现。该程序在高概率下可以以 O（mlog3n）的时间复杂度下求出一个由 m 条边和 n 个点构成的图的最小割，与 Karger 的方法的复杂度相匹配。