Simple Concurrent Labeling Algorithms for Connected Components
Simple Concurrent Labeling Algorithms for Connected Components
复制标题
连接组件的简单并发标记算法
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
R. Tarjan
中科院分区：
文献类型：
--
作者：
Sixue Liu;R. Tarjan
研究了一类同时计算n个点，m个边的图的连通分支的简单算法.我们的算法很容易实现在组合CRCW PRAM或MPC计算模型。对于这类算法中的两个相关算法，我们得到了$\Theta（\lg n）$ step和$\Theta（m \lg n）$ work bounds.对于另外两个，我们得到了$O（\lg^2 n）$ step和$O（m\lg^2 n）$ work bounds，其中一个是紧的。所有算法都比文献中的相关算法简单。我们还指出了一些差距和错误的分析以前的算法。我们的研究结果表明，即使是一个基本的问题，如连接组件仍然有秘密揭示。
We study a class of simple algorithms for concurrently computing the connected components of an $n$-vertex, $m$-edge graph. Our algorithms are easy to implement in either the COMBINING CRCW PRAM or the MPC computing model. For two related algorithms in this class, we obtain $\Theta(\lg n)$ step and $\Theta(m \lg n)$ work bounds. For two others, we obtain $O(\lg^2 n)$ step and $O(m \lg^2 n)$ work bounds, which are tight for one of them. All our algorithms are simpler than related algorithms in the literature. We also point out some gaps and errors in the analysis of previous algorithms. Our results show that even a basic problem like connected components still has secrets to reveal.