Please use this identifier to cite or link to this item:
|Title:||Work-efficient parallel union-find with applications to incremental graph connectivity|
Kun Lung Wu
University of Massachusetts
Iowa State University
IBM Thomas J. Watson Research Center
|Citation:||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol.9833 LNCS, (2016), 561-573|
|Abstract:||© Springer International Publishing Switzerland 2016. 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.|
|Appears in Collections:||Scopus 2016-2017|
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.