Our work titled “Work-Efficient Parallel Union-Find With Applications to Incremental Graph Connectivity” by Simsiri, Tangwongsan, Tirthapura, and Wu was invited for submission to a special issue on Euro-Par 2016 in the journal “Concurrency and Computation: Practice and Experience”. This invitation is reserved for a few of the highest-rated papers in the conference.
This work presents a parallel version of the classic “Union-Find” data structure for maintaining and querying an equivalence relation. Among other applications, the Union-Find data structure can be directly used to maintain whether or not two vertices are connected in a graph, when the graph is changing through the addition of edges.