A LINEAR-TIME ALGORITHM FOR FINDING A MINIMUM SPANNING PSEUDOFOREST

被引：15
作者：
GABOW, HN
TARJAN, RE
机构：
[1] PRINCETON UNIV,DEPT COMP SCI,PRINCETON,NJ 08544
[2] AT&T BELL LABS,MURRAY HILL,NJ 07974
来源：
INFORMATION PROCESSING LETTERS | 1988年 / 27卷 / 05期
关键词：
D O I：
10.1016/0020-0190(88)90089-0
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
引用
收藏
页码：259 / 263
页数：5
相关论文
共 14 条
[1]  
Berge C, 1985, GRAPHS
[2]   IMPLEMENTATION AND ANALYSIS OF BINOMIAL QUEUE ALGORITHMS [J].
BROWN, MR .
SIAM JOURNAL ON COMPUTING, 1978, 7 (03) :298-319
[3]  
Fredman M. L., 1984, 25th Annual Symposium on Foundations of Computer Science (Cat. No. 84CH2085-9), P338, DOI 10.1109/SFCS.1984.715934
[4]  
FREDMAN ML, IN PRESS J ACM
[5]   EFFICIENT ALGORITHMS FOR FINDING MINIMUM SPANNING-TREES IN UNDIRECTED AND DIRECTED-GRAPHS [J].
GABOW, HN ;
GALIL, Z ;
SPENCER, T ;
TARJAN, RE .
COMBINATORICA, 1986, 6 (02) :109-122
[6]  
GOLDBERG AV, 1987, 19TH P ANN ACM S THE, P315
[7]  
Harary F., 1969, GRAPH THEORY, DOI DOI 10.1201/9780429493768
[8]   TRAVELING-SALESMAN PROBLEM AND MINIMUM SPANNING TREES [J].
HELD, M ;
KARP, RM .
OPERATIONS RESEARCH, 1970, 18 (06) :1138-&
[9]  
Lawler E.L., 1976, COMBINATORIAL OPTIMI
[10]   LINEAR ALGORITHMS FOR EDGE-COLORING TREES AND UNICYCLIC GRAPHS [J].
MITCHELL, S ;
HEDETNIEMI, S .
INFORMATION PROCESSING LETTERS, 1979, 9 (03) :110-112
12