Local flow partitioning for faster edge connectivity

We study the problem of computing a minimum cut in a simple, undirected graph and give a deterministic O(m log2n log log2n) time algorithm. This improves both on the best previously known deterministic running time of O(m log12n) (Kawarabayashi and Thorup [12]) and the best previously known randomized running time of O(m log3n) (Karger [11]) for this problem, though Karger's algorithm can be further applied to weighted graphs.