# A Simple Algorithm for Minimum Cuts in Near-Linear Time

arXiv: https://arxiv.org/abs/1908.11829 · HTML: https://mlsanity.com/paper/1908.11829/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Aug 2019.

## Built on by (most cited first, 1 of 1)

- [Extensions of Karger's Algorithm: Why They Fail in Theory and How They Are Useful in Practice](https://mlsanity.com/paper/2110.02750/) (2021)

## Abstract (arXiv)

We consider the minimum cut problem in undirected, weighted graphs. We give a simple algorithm to find a minimum cut that 2-respects (cuts two edges of) a spanning tree T of a graph G. This procedure can be used in place of the complicated subroutine given in Karger's near-linear time minimum cut algorithm (J. ACM, 2000). We give a self-contained version of Karger's algorithm with the new procedure, which is easy to state and relatively simple to implement. It produces a minimum cut on an m-edge, n-vertex graph in O(m log3 n) time with high probability, matching the complexity of Karger's approach.