Parallel Minimum Cuts in O ( m log 2 n ) Work and Low Depth
Daniel K. Anderson, Guy E. Blelloch · 2021
We present a randomized O(m łog^2 n) work, O(polylog n) depth parallel algorithm for minimum cut. This algorithm matches the work bounds of a recent sequential algorithm by Gawrychowski, Mozes, and Weimann [ICALP'20], and improves on the previously best parallel algorithm by Geissmann and Gianinazzi [SPAA'18], which performs O(m łog^4 n) work in O(polylog n) depth.