We study the problem of finding connected components in the Adaptive Massively Parallel Computation (AMPC) model. We show that when we require the total space to be linear in the size of the input graph the problem can be solved in $O(\log^* n)$ rounds in forests (with high probability) and $2^{O(\log^* n)}$ expected rounds in general graphs. This improves upon an existing $O(\log \log_{m/n} n)$ round algorithm. For the case when the desired number of rounds is constant we show that both problems can be solved using $\Theta(m + n \log^{(k)} n)$ total space in expectation (in each round), where $k$ is an arbitrarily large constant and $\log^{(k)}$ is the $k$-th iterate of the $\log_2$ function. This improves upon existing algorithms requiring $\Omega(m + n \log n)$ total space.
翻译：----
我们研究了在自适应大规模并行计算模型中找到连通分量的问题。我们证明，当我们要求总空间与输入图的大小成比例时，该问题可以在森林中以高概率在$O(\log^* n)$轮内解决，在一般图中期望需要$2^{O(\log^* n)}$轮。这比现有的$O(\log \log_{m/n} n)$轮算法更优。对于所需轮数为常数的情况，我们表明这两个问题都可以在期望下使用$ \Theta(m + n \log^{(k)} n)$总空间解决（在每一轮），其中$k$是任意大的常数，$ \log^{(k)}$是$\log_2$函数的第$k$次迭代。这比需要$\Omega(m + n \log n)$总空间的现有算法更优。
相关内容
微信扫码咨询专知VIP会员