Deterministic Near-Linear Time Minimum Cut in Weighted Graphs
Monika Rauch Henzinger, Jason Li, Satish S. Rao, Di Wang · Society for Industrial and Applied Mathematics eBooks · 2024
In 1996, Karger [Kar96] gave a startling randomized algorithm that finds a minimum-cut in a (weighted) graph in time O(m log3 n) which he termed near-linear time meaning linear (in the size of the input) times a polylogarthmic factor. In this paper, we give the first deterministic algorithm which runs in near-linear time for weighted graphs.