Provably Fast and Space-Efficient Parallel Biconnectivity

Xiaojun Dong, Letong Wang, Yan Gu +1

Biconnectivity is one of the most fundamental graph problems. The canonical parallel biconnectivity algorithm is the Tarjan-Vishkin algorithm, which has $O(n+m)$ optimal work (numb…