TRANSITIVE COMPACTION IN PARALLEL VIA BRANCHINGS

被引:10
作者
GIBBONS, P
KARP, R
RAMACHANDRAN, V
SOROKER, D
TARJAN, R
机构
[1] UNIV CALIF BERKELEY,DIV COMP SCI,BERKELEY,CA 94720
[2] UNIV ILLINOIS,COORDINATED SCI LAB,URBANA,IL 61801
[3] IBM CORP,ALMADEN RES CTR,SAN JOSE,CA 95114
[4] PRINCETON UNIV,DEPT COMP SCI,PRINCETON,NJ 08544
[5] AT&T BELL LABS,MURRAY HILL,NJ 07974
基金
美国国家科学基金会;
关键词
D O I
10.1016/0196-6774(91)90026-U
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We study the following problem: given a strongly connected digraph, find a minimal strongly connected spanning subgraph of it. Our main result is a parallel algorithm for this problem, which runs in polylog parallel time and uses O(n3) processors on a PRAM. Our algorithm is simple and the major tool it uses is computing a minimum-weight branching with zero-one weights. We also present sequential algorithms for the problem that run in time O(m + n · log n). © 1991.
引用
收藏
页码:110 / 125
页数:16
相关论文
共 23 条
[1]  
Aho A. V., 1972, SIAM Journal on Computing, V1, P131, DOI 10.1137/0201008
[2]   A FAST AND SIMPLE RANDOMIZED PARALLEL ALGORITHM FOR THE MAXIMAL INDEPENDENT SET PROBLEM [J].
ALON, N ;
BABAI, L ;
ITAI, A .
JOURNAL OF ALGORITHMS, 1986, 7 (04) :567-583
[3]  
AMATO N, 1988, UNPUB IMPROVED PROCE
[4]   OPTIMUM BRANCHINGS [J].
EDMONDS, J .
JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS SECTION B-MATHEMATICAL SCIENCES, 1967, B 71 (04) :233-+
[5]  
Edmonds J., 1973, COMBINATORIAL ALGORI, P91
[6]  
Eswaran K. P., 1976, SIAM Journal on Computing, V5, P653, DOI 10.1137/0205044
[7]   A LINEAR-TIME ALGORITHM FOR A SPECIAL CASE OF DISJOINT SET UNION [J].
GABOW, HN ;
TARJAN, RE .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1985, 30 (02) :209-221
[8]  
GABOW HN, 1986, COMBINATORICA, V6, P106
[9]  
Garey M. R., 1979, COMPUTERS INTRACTABI
[10]  
Goldberg M., 1987, 28th Annual Symposium on Foundations of Computer Science (Cat. No.87CH2471-1), P161, DOI 10.1109/SFCS.1987.2