Concurrent Skip Lists for Dynamic Forest Connectivity
In the problem of dynamic forest connectivity, we strive to answer connectivity queries on a forest as the forest undergoes edge insertions
and deletions. There are many existing sequential data structures for this problem, including Euler tour trees. However, none of the
sequential approaches can exploit parallelism in the batch setting in which a batch of edges are inserted or deleted from the graph at once.
We develop a work-efficient, polylogarithmic span implementation of a batch parallel Euler tour tree.
The core of our implementation is a concurrent skip list capable of batch joins and batch splits. We show that a batch of either m joins and
m splits over n nodes achieves O(m log(n/m)) work and O(log(n)) span. This concurrent skip list may also be augmented, which hints at an
approach to batch parallel dynamic connectivity for general undirected graphs. We measure the performance of our data structures
empirically as well.