Simple jQuery Dropdowns
Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorNatcha Simsirien_US
dc.contributor.authorKanat Tangwongsanen_US
dc.contributor.authorSrikanta Tirthapuraen_US
dc.contributor.authorKun Lung Wuen_US
dc.contributor.otherUniversity of Massachusettsen_US
dc.contributor.otherMahidol Universityen_US
dc.contributor.otherIowa State Universityen_US
dc.contributor.otherIBM Thomas J. Watson Research Centeren_US
dc.identifier.citationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol.9833 LNCS, (2016), 561-573en_US
dc.description.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.en_US
dc.rightsMahidol Universityen_US
dc.subjectComputer Scienceen_US
dc.titleWork-efficient parallel union-find with applications to incremental graph connectivityen_US
dc.typeConference Paperen_US
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.