Connected Components in O (log^3/2 n) Parallel Time for the CREW PRAM
Connected Components in O (log^3/2 n) Parallel Time for the CREW PRAM
复制标题
CREW PRAM 的连接组件在 O (log^3/2 n) 并行时间内
DOI：
10.1006/jcss.1997.1291
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
P. Metaxas
中科院分区：
文献类型：
--
作者：
Donald B. Johnson;P. Metaxas
求无向图G =（V，E）onn=的连通分支|V|顶点和m =| E|边缘是基本的计算问题。CREW PRAM模型的最著名的并行算法运行在O（log 2n）时间使用n2/log 2n处理器。对于CRCW PRAM模型，其中并发写是允许的，最有名的算法运行在O（logn）时间使用略多于（n+m）/logn处理器。在较弱的CREW模型上模拟该算法，使其运行时间增加到O（log 2n）。本文提出了一个简单的算法，在n +mCREW处理器上，时间复杂度为O（log ~ 3/2n）。为该模型寻找ano（log 2n）并行连通性算法是一个多年来的公开问题。
Finding the connected components of an undirected graphG=(V, E) onn=|V| vertices andm=|E| edges is a fundamental computational problem. The best known parallel algorithm for the CREW PRAM model runs inO(log2n) time usingn2/log2nprocessors. For the CRCW PRAM model, in which concurrent writing is permitted, the best known algorithm runs inO(logn) time using slightly more than (n+m)/lognprocessors. Simulating this algorithm on the weaker CREW model increases its running time toO(log2n). We present here a simple algorithm that runs inO(log3/2n) time usingn+mCREW processors. Finding ano(log2n) parallel connectivity algorithm for this model was an open problem for many years.