Minimum Cut in $O(m\log^2 n)$ Time Article Swipe

View

Related Concepts

Combinatorics Binary logarithm Minimum cut Time complexity Spanning tree Mathematics Minimum spanning tree Vertex (graph theory) Undirected graph Log-log plot Randomized algorithm Running time Graph Discrete mathematics Algorithm

Paweł Gawrychowski , Shay Mozes , Oren Weimann ·

YOU? · · 2019 · Open Access · · DOI: https://doi.org/10.4230/lipics.icalp.2020.57 · OA: W3037081898

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² n) time. This is the first improvement to Karger’s celebrated O(m log³ n) time algorithm from 1996. Our main technical contribution is a deterministic 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.