Minimum Cut in O(mlog^2 n) Time

11/04/2019

∙

by   Paweł Gawrychowski, et al.

∙

0

∙

share

We give a randomized algorithm that finds a minimum cut in an undirected weighted m-edge n-vertex graph G with high probability in O(m log^2 n) time. This is the first improvement to Karger's celebrated O(m log^3 n) time algorithm from 1996. Our main technical contribution is an O(m log n) time algorithm that, given a spanning tree T of G, finds a minimum cut of G that 2-respects (cuts two edges of) T.