2019/03/31 by Umut A. Acar, Daniel Anderson, Guy E. Blelloch +1 · 1 citation
Computer Science · #cs.DS
paper · pdf · doi:10.1145/3323165.3323196
published as Proceedings of The 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '19) (2019) 381-392 · This is the full version of the paper appearing in the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2019
arxiv created 2020/05/17 · arxiv updated 2020/05/19
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 most well known sequential algorithm for dynamic connectivity is the elegant level-set algorithm of Holm, de Lichtenberg and Thorup (HDT), which achieves O(log2 n) amortized time per edge insertion or deletion, and O(log n / loglog n) time per query. We design a parallel batch-dynamic connectivity algorithm that is work-efficient with respect to the HDT algorithm for small batch sizes, and is asymptotically faster when the average batch size is sufficiently large. Given a sequence of batched updates, where Δ is the average batch size of all deletions, our algorithm achieves O(log n log(1 + n / Δ)) expected amortized work per edge insertion and deletion and O(log3 n) depth w.h.p. Our algorithm answers a batch of k connectivity queries in O(k log(1 + n/k)) expected work and O(log n) depth w.h.p. To the best of our knowledge, our algorithm is the first parallel batch-dynamic algorithm for connectivity.