Provably Fast and Space-Efficient Parallel Biconnectivity (Abstract)
Xiaojun Dong, L. Wang, Yan Gu, Yihan Sun · 2023
We propose the first parallel biconnectivity algorithm (FAST-BCC) that has optimal work, polylogarithmic span, and is space-efficient. Our algorithm creates a skeleton graph based on any spanning tree of the input graph. Then we use the connectivity information of the skeleton to compute the biconnectivity of the original input. We carefully analyze the correctness of our algorithm.