Please use this identifier to cite or link to this item:
Title: Work-efficient parallel union-find with applications to incremental graph connectivity
Authors: Natcha Simsiri
Kanat Tangwongsan
Srikanta Tirthapura
Kun Lung Wu
University of Massachusetts
Mahidol University
Iowa State University
IBM Thomas J. Watson Research Center
Keywords: Computer Science;Mathematics
Issue Date: 1-Jan-2016
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.
ISSN: 16113349
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.