Parallel Minimum Cuts in $O(m{\log }^2(n))$ Work and Low Depth

Daniel Anderson, Guy E. Blelloch

We present a randomized $O(m{\log }^{2}n)$ work, $O(\text{polylog }n)$ depth parallel algorithm for minimum cut. This algorithm matches the work bounds of a recent sequential algorit…