Fast and Theoretically-Efficient Batch-Parallel Link-Cut Trees, Euler Tour Trees, and Treaps

Quinten De Man, Laxman Dhulipala

Parallel batch-dynamic trees are a fundamental building block in recent theoretical and practical advances in dynamic graph algorithms. However, all existing parallel batch-dynamic…