.png){kind=icon}
.png){kind=icon}
Return
Towards Scalable and Practical Batch-Dynamic Connectivity
.png){kind=icon}
PRE
AI
DOI：10.14778/3712221.3712250.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We study the problem of dynamically maintaining the connected components of an undirected graph subject to edge insertions and deletions. We give the first parallel algorithm for the problem that is work-efficient, supports batches of updates, runs in polylogarithmic depth, and uses only linear total space. The existing algorithms for the problem either use super-linear space, do not come with strong theoretical bounds, or are not parallel. On the empirical side, we provide the first implementation of the cluster forest algorithm, the first linear-space and polylogarithmic update time algorithm for dynamic connectivity. Experimentally, we find that our algorithm uses up to 19.7x less space and is up to 6.2x faster than the level-set algorithm of Holm, de Lichtenberg, and Thorup, arguably the most widely-implemented dynamic connectivity algorithm with strong theoretical guarantees.
Journal
P
IF:
3.3
Papers:
556
Citations:
1.2W
View more organizations