Minimum Cut in O(mlog2 n) Time
Not on the map. Why?
Abstract (arXiv)
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 log2 n) time. This is the first improvement to Karger's celebrated O(m log3 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.
Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). First posted on arXiv 4 Nov 2019.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 1; 2022: 2; 2023: 0; 2024: 0; 2025: 1.
4 papers.
- 2022On the Robustness of CountSketch to Adaptive Inputscited by 5
- 2022Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputscited by 2
- 2021Extensions of Karger's Algorithm: Why They Fail in Theory and How They Are Useful in Practicecited by 0
- 2025The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for ℓ2 Norm Estimationcited by 0
- 2025The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for ℓ2 Norm Estimation22 Jul 2025
- 2022Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs3 Jul 2022
- 2022On the Robustness of CountSketch to Adaptive Inputs28 Feb 2022
- 2021Extensions of Karger's Algorithm: Why They Fail in Theory and How They Are Useful in Practice5 Oct 2021