Siddhartha Jayanti: Concurrent Disjoint Set Union

A famous result in sequential data structures that the Union-Find object can be implemented in amortized inverse-Ackermann work per operation. Anderson and Woll showed that the algorithm can be made concurrent with a linear work-complexity overhead (in the number of processors). I will present our randomized algorithm which is simpler, and requires only logarithmic overhead, and touch on further improvements and some potential applications for the data structure. (This was joint work with Professor Robert Tarjan, done at Princeton University.)