Work-Efficient Parallel Union-Find with Applications to Incremental Graph Connectivity
Work-Efficient Parallel Union-Find with Applications to Incremental Graph Connectivity
复制标题
高效工作的并行并查找及其在增量图连接中的应用
DOI：
10.1007/978-3-319-43659-3_41
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Kun
中科院分区：
文献类型：
--
作者：
Natcha Simsiri;Kanat Tangwongsan;Srikanta Tirthapura;Kun
在无向图上，如何快速回答是否连接两个顶点，同时允许逐步添加更多边缘？这是研究良好的增量图连接性IGC问题，这是一个基本问题，可以使用经典联合信息问题的解决方案有效地解决。由于需要处理更大和快速变化的图表的需要，本文介绍了第一个用于IGC的共享记忆并行算法，并且等效地，联合信息可证明工作效率，即没有比顺序最佳的工作更大的工作，并且具有polylogarithmicicalmicicalmicicalmicic平行深度。它在没有锁或投机执行的情况下并行执行路径压缩。我们还提出了一种更简单的算法，其理论属性较差，但更易于实现，并且具有良好的实践性能。
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.