Parallel Minimum Cuts in Near-linear Work and Low Depth
Parallel Minimum Cuts in Near-linear Work and Low Depth
We present the first near-linear work and poly-logarithmic depth algorithm for computing a minimum cut in a graph, while previous parallel algorithms with poly-logarithmic depth required at least quadratic work in the number of vertices. In a graph with $n$ vertices and $m$ edges, our algorithm computes the correct result …