TY - GEN
T1 - Work-efficient parallel union-find with applications to incremental graph connectivity
AU - Simsiri, Natcha
AU - Tangwongsan, Kanat
AU - Tirthapura, Srikanta
AU - Wu, Kun Lung
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2016.
PY - 2016
Y1 - 2016
N2 - On an undirected graph, how can one quickly answer whether two vertices are connected while allowing more edges to be added incrementally? This is the well-studied incremental graph connectivity (IGC) problem, a fundamental problem that can be efficiently solved using solutions to the classical union-find problem. Motivated by the need to handle larger and rapidly-changing graphs, this paper presents the first shared-memory parallel algorithm for IGC and equivalently, Union-Find that is provably work-efficient (i.e., does no more work than the sequential optimal) and has polylogarithmic parallel depth. It performs path compression in parallel without a lock or speculative execution. We also present a simpler algorithm with slightly worse theoretical properties, but which is easier to implement, and has good practical performance.
AB - On an undirected graph, how can one quickly answer whether two vertices are connected while allowing more edges to be added incrementally? This is the well-studied incremental graph connectivity (IGC) problem, a fundamental problem that can be efficiently solved using solutions to the classical union-find problem. Motivated by the need to handle larger and rapidly-changing graphs, this paper presents the first shared-memory parallel algorithm for IGC and equivalently, Union-Find that is provably work-efficient (i.e., does no more work than the sequential optimal) and has polylogarithmic parallel depth. It performs path compression in parallel without a lock or speculative execution. We also present a simpler algorithm with slightly worse theoretical properties, but which is easier to implement, and has good practical performance.
UR - https://www.scopus.com/pages/publications/84984806940
U2 - 10.1007/978-3-319-43659-3_41
DO - 10.1007/978-3-319-43659-3_41
M3 - Conference contribution
AN - SCOPUS:84984806940
SN - 9783319436586
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 561
EP - 573
BT - Parallel Processing - 22nd International Conference on Parallel and Distributed Computing, Euro-Par 2016, Proceedings
A2 - Dutot, Pierre-François
A2 - Trystram, Denis
PB - Springer Verlag
T2 - 22nd International Conference on Parallel and Distributed Computing, Euro-Par 2016
Y2 - 24 August 2016 through 26 August 2016
ER -