Towards Scalable and Practical Batch-Dynamic Connectivity
Summary: First work-efficient parallel batch-dynamic connectivity algorithm with polylogarithmic depth and linear space. Its cluster-forest implementation uses up to 19.7× less space and runs 6.2× faster than Holm–de Lichtenberg–Thorup. (summarized by gpt-5.6-luna on Jul 24 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Quinten De Man (University of Maryland)
- 2. Laxman Dhulipala (University of Maryland)
- 3. Adam Karczmarz (IDEAS NCBR; University of Warsaw)
- 4. Jakub Łącki (Google)
- 5. Julian Shun (Massachusetts Institute of Technology)
- 6. Zhongqi Wang (University of Maryland)
BibTeX Citation
@article{man_vldb25,
title = {{Towards Scalable and Practical Batch-Dynamic Connectivity}},
author = {De Man, Quinten and Dhulipala, Laxman and Karczmarz, Adam and Łącki, Jakub and Shun, Julian and Wang, Zhongqi},
journal = {PVLDB},
series = {{VLDB} '25},
volume = {18},
number = {3},
pages = {889--901},
doi = {10.14778/3712221.3712250},
url = {https://doi.org/10.14778/3712221.3712250},
year = {2025}
}Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 5 of 5 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 3,020 | Dynamic Density Based Clustering | 2017 | SIGMOD | 7.8445412e-05 |
| 3,154 | Dynamic Spanning Trees for Connectivity Queries on Fully-dynamic Undirected Graphs | 2022 | VLDB | 7.6959807e-05 |
| 3,778 | Terrace: A Hierarchical Graph Container for Skewed Dynamic Graphs | 2021 | SIGMOD | 7.1334329e-05 |
| 4,423 | Dynamic Structural Clustering on Graphs | 2021 | SIGMOD | 6.7107949e-05 |
| 7,862 | ConnectIt: A Framework for Static and Incremental Parallel Graph Connectivity Algorithms | 2021 | VLDB | 5.5302333e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 8,623 | A Near-Optimal Approach to Edge Connectivity-Based Hierarchical Graph Decomposition | 2022 | VLDB |
| 2 | 7,578 | Minimum Strongly Connected Subgraph Collection in Dynamic Graphs | 2024 | VLDB |
| 3 | 9,387 | Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs | 2024 | VLDB |
| 4 | 13,409 | Concurrent Link-Cut Trees | 2022 | SIGMOD |
| 5 | 5,540 | Efficiently Computing k-Edge Connected Components via Graph Decomposition | 2013 | SIGMOD |
| 6 | 7,862 | ConnectIt: A Framework for Static and Incremental Parallel Graph Connectivity Algorithms | 2021 | VLDB |
| 7 | 8,657 | An Experimental Comparison of Tree-data Structures for Connectivity Queries on Fully-dynamic Undirected Graphs | 2025 | SIGMOD |
| 8 | 10,671 | Minimum Spanning Tree Maintenance in Dynamic Graphs | 2025 | SIGMOD |
| 9 | 3,154 | Dynamic Spanning Trees for Connectivity Queries on Fully-dynamic Undirected Graphs | 2022 | VLDB |
| 10 | 11,198 | Constant-time Connectivity Querying in Dynamic Graphs | 2024 | SIGMOD |