Minimum Cut in O(mlog² n) Time

2019/11/04 by Paweł Gawrychowski, Shay Mozes, Gawrychowski, Paweł +3 · 1 voice · 1 citation
#cs.DS

paper · pdf · doi:10.48550/arxiv.1911.01145

Abstract

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.

Cited by

• Simple Algorithms for Fully Dynamic Edge Connectivity

Discussions

• Runtime improvement for Minimum Cut algorithm first time in 25 years (2019) [hn, 153 points, 56 comments]

Related

• A Note on a Recent Algorithm for Minimum Cut
• A Simple Algorithm for Minimum Cuts in Near-Linear Time
• Minimum Cuts in Near-Linear Time
• Fast and Deterministic Approximations for k-Cut
• Breaking the O(mn)-Time Barrier for Vertex-Weighted Global Minimum Cut