Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs

Andrés López-Martínez, Sagnik Mukhopadhyay, Danupon Nanongkai

We present the first work-optimal polylogarithmic-depth parallel algorithm for the minimum cut problem on non-sparse graphs. For $m\ge n^{1+\epsilon }$ for any constant $\epsilon >0$, our algorit…