Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time
Ken‐ichi Kawarabayashi, Mikkel Thorup · 2015
We present a deterministic near-linear time algorithm that computes the edge-connectivity and finds a minimum cut for a simple undirected unweighted graph G with n vertices and m edges. This is the first o(mn) time deterministic algorithm for the problem. In near-linear time we can also construct the classic cactus representation of all minimum cuts.