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: 6391
Venue: SIGMOD
Year: 2022
Pagerank: -
Overall Rank: 13,220 | 8.12%
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,255	Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs	2024	VLDB	5.3572577e-05
9,625	An Experimental Comparison of Tree-data Structures for Connectivity Queries on Fully-dynamic Undirected Graphs	2025	SIGMOD	5.3018378e-05
10,915	Topology-aware Parallel Joins	2024	PODS	5.1725247e-05
7,733	ConnectIt: A Framework for Static and Incremental Parallel Graph Connectivity Algorithms	2021	VLDB	5.615884e-05
3,120	Dynamic Spanning Trees for Connectivity Queries on Fully-dynamic Undirected Graphs	2022	VLDB	7.7925965e-05
7,615	Mining Tree-Structured Data on Multicore Systems	2009	VLDB	5.6406426e-05
3,013	High-Concurrency Locking in R-Trees	1995	VLDB	7.9164773e-05
10,988	Constant-time Connectivity Querying in Dynamic Graphs	2024	SIGMOD	5.1725247e-05
4,721	Concurrency Control Mechanisms and the Serializability of Concurrent Tree Algorithms	1984	PODS	6.6082371e-05
10,886	Towards Scalable and Practical Batch-Dynamic Connectivity	2025	VLDB	5.1725247e-05