Concurrent Link-Cut Trees

Summary: Explores parallelizing link-cut trees to maintain a dynamic forest under concurrent link and cut operations. It uses path decomposition to store root-to-node paths in binary balanced trees, achieving logarithmic time and enabling scalable parallel root, link, and cut queries. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6390
Venue: SIGMOD
Year: 2022
Pagerank: -
Overall Rank: 13,206 | 8.13%
DOI: 10.1145/3514221.3520247

Incoming Non-self Citations Over Time

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

Authors

1. Mihail Stoian

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,239	Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs	2024	VLDB	4.3690661e-05
9,641	An Experimental Comparison of Tree-data Structures for Connectivity Queries on Fully-dynamic Undirected Graphs	2025	SIGMOD	4.3109001e-05
10,911	Topology-aware Parallel Joins	2024	PODS	4.1945683e-05
7,871	ConnectIt: A Framework for Static and Incremental Parallel Graph Connectivity Algorithms	2021	VLDB	4.6308128e-05
3,146	Dynamic Spanning Trees for Connectivity Queries on Fully-dynamic Undirected Graphs	2022	VLDB	7.477231e-05
7,790	Mining Tree-Structured Data on Multicore Systems	2009	VLDB	4.650649e-05
3,039	High-Concurrency Locking in R-Trees	1995	VLDB	7.6708607e-05
10,985	Constant-time Connectivity Querying in Dynamic Graphs	2024	SIGMOD	4.1945683e-05
3,596	Concurrency Control Mechanisms and the Serializability of Concurrent Tree Algorithms	1984	PODS	6.9357398e-05
10,882	Towards Scalable and Practical Batch-Dynamic Connectivity	2025	VLDB	4.1945683e-05