COMPUTING CONNECTED COMPONENTS ON PARALLEL COMPUTERS

被引：156

作者：

HIRSCHBERG, DS

CHANDRA, AK

SARWATE, DV

机构：

[1] IBM CORP,THOMAS J WATSON RES CTR,YORKTOWN HTS,NY 10598

[2] UNIV ILLINOIS,COORDINATED SCI LAB,URBANA,IL 61801

来源：

COMMUNICATIONS OF THE ACM | 1979年 / 22卷 / 08期

关键词：

algorithms; connected component; graph theory; parallel processing; transitive closure;

D O I：

10.1145/359138.359141

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We present a parallel algorithm which uses n2 processors to find the connected components of an undirected graph with n vertices in time O(log2n). An O(log2n) time bound also can be achieved using only n⌈n/⌈log2n⌉⌉ processors. The algorithm can be used to find the transitive closure of a symmetric Boolean matrix. We assume that the processors have access to a common memory. Simultaneous access to the same location is permitted for fetch instructions but not for store instructions. © 1979, ACM. All rights reserved.

引用

页码：461 / 464

页数：4

共 16 条

[1] Aho A. V., 1974, DESIGN ANAL COMPUTER
[2] BAUDET G, 1978, IEEE T COMPUT, V27, P84, DOI 10.1109/TC.1978.1674957
[3] PARALLEL EVALUATION OF GENERAL ARITHMETIC EXPRESSIONS
BRENT, RP
[J]. JOURNAL OF THE ACM, 1974, 21 (02) : 201 - 206
[4] CHANDRA AK, 1976, RC6193 IBM TECH REP
[5] Csanky L., 1976, SIAM Journal on Computing, V5, P618, DOI 10.1137/0205040
[6] FAST PARALLEL SORTING ALGORITHMS
HIRSCHBERG, DS
[J]. COMMUNICATIONS OF THE ACM, 1978, 21 (08) : 657 - 661
[7] COMPLEXITY OF PARALLEL EVALUATION OF LINEAR RECURRENCES
HYAFIL, L
KUNG, HT
[J]. JOURNAL OF THE ACM, 1977, 24 (03) : 513 - 521
[8] CELLULAR ARRAYS FOR SOLUTION OF GRAPH PROBLEMS
LEVITT, KN
KAUTZ, WH
[J]. COMMUNICATIONS OF THE ACM, 1972, 15 (09) : 789 - &
[9] MUNRO I, 1973, J COMP SYST SCI, V7, P183
[10] Pan V. Ya., 1978, 19th Annual Symposium on Foundations of Computer Science, P166, DOI 10.1109/SFCS.1978.34

← 1 2 →