Minimum cuts in near-linear time

We significantly improve known time bounds for solving the minimum cut prob lem on undirected graphs. We use a "semiduality" between minimum cuts and m aximum spanning tree packings combined with our previously developed random sampling techniques. We give a randomized (Monte Carlo) algorithm that fin ds a minimum cut in an m-edge, n-vertex graph with high probability in O(m log(3) n) time. We also give a simpler randomized algorithm that finds all minimum cuts with high probability in O(n(2) log n) time. This variant has an optimal RN6 parallelization. Both variants improve on the previous best time bound of O(n(2) log(3) n). Other applications of the tree-packing appr oach are new, nearly tight bounds on the number of near-minimum cuts a grap h may have and a new data structure for representing them in a space-effici ent manner.