Parallel Batch-Dynamic Graph Connectivity
Umut A. Acar, Daniel K. Anderson, Guy E. Blelloch, Laxman Dhulipala · 2019
In this paper, we study batch parallel algorithms for the dynamic connectivity problem, a fundamental problem that has received considerable attention in the sequential setting. The best sequential algorithm for dynamic connectivity is the elegant level-set algorithm of Holm, de Lichtenberg and Thorup (HDT), which achieves O(łog2 n) amortized time per edge insertion or deletion, and O(łog n) time per query.