Publication: Work-efficient parallel union-find with applications to incremental graph connectivity
Issued Date
2016-01-01
Resource Type
ISSN
16113349
03029743
03029743
Other identifier(s)
2-s2.0-84984806940
Rights
Mahidol University
Rights Holder(s)
SCOPUS
Bibliographic Citation
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol.9833 LNCS, (2016), 561-573
Suggested Citation
Natcha Simsiri, Kanat Tangwongsan, Srikanta Tirthapura, Kun Lung Wu Work-efficient parallel union-find with applications to incremental graph connectivity. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol.9833 LNCS, (2016), 561-573. doi:10.1007/978-3-319-43659-3_41 Retrieved from: https://repository.li.mahidol.ac.th/handle/20.500.14594/40572
Research Projects
Organizational Units
Authors
Journal Issue
Thesis
Title
Work-efficient parallel union-find with applications to incremental graph connectivity
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.