Our paper titled “Work-Efficient Parallel Union-Find” has been accepted to the journal Concurrency and Computation: Practice and Experience. The authors are Simsiri, Tangwongsan, Tirthapura, and Wu.
This paper presents a shared-memory parallel algorithm for the fundamental “Union-Find” problem for maintaining equivalence classes. The uniqueness of this solution is that it is the first parallel algorithm whose total work across all processors is of the same order as the computational cost of the best sequential algorithm for union-find, which uses “path compression” (whose now-famous analysis by Tarjan has shown it to be near-constant time per operation).