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.