Constant-time Connectivity Querying in Dynamic Graphs

Summary: Constant-time connectivity queries for fully dynamic undirected graphs using a novel hybrid of per-component spanning trees and a disjoint-set (DS) tree. Concurrent maintenance of both trees yields true constant query time and significantly improved edge insert/delete times, outperforming the D-tree on real datasets. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6979
Venue: SIGMOD
Year: 2024
Pagerank: 4.1945683e-05
Overall Rank: 10,985 | 23.58%
DOI: 10.1145/3698805

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,383	Minimum Spanning Tree Maintenance in Dynamic Graphs	2025	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
246	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD	0.00030949575
279	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00029113513
1,777	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	0.00010589591
1,880	TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph	2013	SIGMOD	0.00010226347
3,146	Dynamic Spanning Trees for Connectivity Queries on Fully-dynamic Undirected Graphs	2022	VLDB	7.477231e-05
4,478	Reachability Querying: An Independent Permutation Labeling Approach	2014	VLDB	6.1506256e-05
6,657	On Querying Historical Connectivity in Temporal Graphs	2024	SIGMOD	4.9720132e-05
6,795	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	4.9242446e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,366	Minimum Spanning Trees in Temporal Graphs	2015	SIGMOD	5.5460085e-05
1,777	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	0.00010589591
6,207	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD	5.1572428e-05
4,970	On Querying Connected Components in Large Temporal Graphs	2023	SIGMOD	5.7945079e-05
6,725	Maximal D-truss Search in Dynamic Directed Graphs	2023	VLDB	4.9484066e-05
6,657	On Querying Historical Connectivity in Temporal Graphs	2024	SIGMOD	4.9720132e-05
10,383	Minimum Spanning Tree Maintenance in Dynamic Graphs	2025	SIGMOD	4.1945683e-05
10,882	Towards Scalable and Practical Batch-Dynamic Connectivity	2025	VLDB	4.1945683e-05
9,641	An Experimental Comparison of Tree-data Structures for Connectivity Queries on Fully-dynamic Undirected Graphs	2025	SIGMOD	4.3109001e-05
3,146	Dynamic Spanning Trees for Connectivity Queries on Fully-dynamic Undirected Graphs	2022	VLDB	7.477231e-05