Local Flow Partitioning for Faster Edge Connectivity

Monika Henzinger, Satish Rao, Di Wang

We study the problem of computing a minimum cut in a simple, undirected graph and give a deterministic $O(m{\log }^{2}n\log {\log }^{2}n)$ time algorithm. This improves both on the best p…