Today I read a paper titled “Minimum Cuts in Near-Linear Time”

The abstract is:

* We significantly improve known time bounds for solving the minimum cut problem on undirected graphs.*

*We use a “semi-duality” between minimum cuts and maximum spanning tree packings combined with our previously developed random sampling techniques.*

*We give a randomized algorithm that finds 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 RNC parallelization.*

*Both variants improve on the previous best time bound of O(n^2 log^3 n).*

*Other applications of the tree-packing approach are new, nearly tight bounds on the number of near minimum cuts a graph may have and a new data structure for representing them in a space-efficient manner.*