Connected Components on a PRAM in Log Diameter Time
Connected Components on a PRAM in Log Diameter Time
复制标题
PRAM 上的连接组件（以日志直径时间表示）
DOI：
10.1145/3350755.3400249
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Zhong, Peilin
中科院分区：
文献类型：
--
作者：
Liu, Sixue Cliff;Tarjan, Robert E.;Zhong, Peilin
我们提出了一个O（log d + log logm/nn）时间的随机PRAM算法，用于计算n-顶点，m-边无向图的最大连通分支直径d。该算法运行在一个ARBITRARY CRCW（并发读，并发写任意写分辨率）PRAM使用O（m）处理器。我们的算法是基于Andoni等人[FOCS'18]和Behnezhad等人[FOCS'19]的突破性结果。他们的算法运行在更强大的MPC模型上，并且依赖于O（1）时间内的排序和计算前缀和，在具有poly（n）处理器的CRCW PRAM上花费Ω（log n / log log n）时间的任务。我们更简单的算法使用有限冲突哈希，不排序或前缀求和。它与Behnezhad等人的算法的时间和空间界限相匹配，人们普遍认为，MPC模型的每个处理器更大的私有内存和无限的本地计算允许比PRAM上的算法更快的算法。我们的研究结果表明，这种额外的权力可能是不必要的，至少对于基本的图形问题，如连接组件和生成森林。
We present an O(log d + log logm/nn)-time randomized PRAM algorithm for computing the connected components of an n-vertex, m-edge undirected graph with maximum component diameter d. The algorithm runs on an ARBITRARY CRCW (concurrent-read, concurrent-write with arbitrary write resolution) PRAM using O(m) processors. The time bound holds with good probability.Our algorithm is based on the breakthrough results of Andoni et al. [FOCS'18] and Behnezhad et al. [FOCS'19]. Their algorithms run on the more powerful MPC model and rely on sorting and computing prefix sums in O(1) time, tasks that take Ω(log n / log log n) time on a CRCW PRAM with poly(n) processors. Our simpler algorithm uses limited-collision hashing and does not sort or do prefix sums. It matches the time and space bounds of the algorithm of Behnezhad et al., who improved the time bound of Andoni et al.It is widely believed that the larger private memory per processor and unbounded local computation of the MPC model admit algorithms faster than that on a PRAM. Our result suggests that such additional power might not be necessary, at least for fundamental graph problems like connected components and spanning forest.
登录
查看更多内容
使用均匀恒定深度电路进行近似计数
影响因子：
1.6
作者：
M. Ajtai
通讯作者：
M. Ajtai
用于查找生成森林和其他基本图连接问题的最佳随机 EREW PRAM 算法
DOI：
10.1006/jagm.2000.1146
发表时间：
1996
期刊：
The journal of physical chemistry. B
影响因子：
--
作者：
S. Halperin;Uri Zwick
通讯作者：
Uri Zwick
用于网状连接并行计算机的连接组件算法
影响因子：
3.7
作者：
S. Goddard;Subodh Kumar;J. Prins
通讯作者：
J. Prins
使用近似算法设计可能忽略处理器分配的并行算法
DOI：
10.1109/sfcs.1991.185439
发表时间：
1991
期刊：
[1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science
影响因子：
--
作者：
M. Goodrich
通讯作者：
M. Goodrich
CREW PRAM 的连接组件在 O (log^3/2 n) 并行时间内
DOI：
10.1006/jcss.1997.1291
发表时间：
1997
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
Donald B. Johnson;P. Metaxas
通讯作者：
P. Metaxas