AN EFFICIENT AND FAST PARALLEL-CONNECTED COMPONENT ALGORITHM
AN EFFICIENT AND FAST PARALLEL-CONNECTED COMPONENT ALGORITHM
复制标题
DOI：
10.1145/79147.214077
复制
发表时间：
1990-07-01
影响因子：
2.5
通讯作者：
WAGNER, RA
中科院分区：
文献类型：
--
作者：
HAN, YJ;WAGNER, RA
提出了一种计算无向图连通分支的并行算法。共享内存计算模型是假定的。对于一个有n个节点的图，算法的时间复杂度为O（e/p+（nlogn）/p+ log 2n）（p个处理机）。该算法可以进一步细化以产生时间复杂度O（H（e，n，p）/p+（nlogn）/（plog（n/p））+log 2n），其中H（e，n，p）非常接近O（e）。这些结果表明，当ne ≥nlogn时，对于up top≤e/log 2n处理机，可获得线性加速比。对于满足inge ≥nlog（*）n的图，使用最多≤nε个处理器，0 ≤ ε < 1，仍能获得线性加速比.如果有更有效的整数排序算法，我们的结果可以进一步改进。
A parallel algorithm for computing the connected components of undirected graphs is presented. Shared memory computation models are assumed. For a graph ofeedges andnnodes, the time complexity of the algorithm is Ο(e/p+ (nlogn)/p+ log2n) withpprocessors. The algorithm can be further refined to yield time complexity Ο(H(e,n,p)/p+ (nlogn)/(plog(n/p)) + log2n), whereH(e, n, p) is very close to Ο(e). These results show that linear speedup can be obtained for up top≤e/log2nprocessors whene≥nlogn. Linear speedup can still be achieved with up top≤nε processors, 0 ≤ ε < 1, for graphs satisfyinge≥nlog(*)n. Our results can be further improved if a more efficient integer sorting algorithm is available.