A PARALLEL ALGORITHM FOR ELIMINATING CYCLES IN UNDIRECTED GRAPHS

被引：9
作者：
KLEIN, P [1 ]
STEIN, C [1 ]
机构：
[1] MIT,COMP SCI LAB,CAMBRIDGE,MA 02139
来源：
INFORMATION PROCESSING LETTERS | 1990年 / 34卷 / 06期
基金：
美国国家科学基金会;
关键词：
cycles; Euler tour; Parallel algorithms; undirected graphs;
D O I：
10.1016/0020-0190(90)90015-P
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We give an efficient parallel algorithm for finding a maximal set of edge-disjoint cycles in an undirected graph. The algorithm can be generalized to handle a weighted version of the problem. © 1990.
引用
收藏
页码：307 / 312
页数：6
相关论文
共 14 条
[1]  
ANDERSON RJ, 1988, LECT NOTES COMPUT SC, V319, P81
[2]  
AWERBUCH B, 1984, 16TH P ANN ACM S THE, P249
[3]  
Berge C., 1979, GRAPHS HYPERGRAPHS
[4]  
COLE R, 1988, LECT NOTES COMPUT SC, V319, P91
[5]   THEORETICAL IMPROVEMENTS IN ALGORITHMIC EFFICIENCY FOR NETWORK FLOW PROBLEMS [J].
EDMONDS, J ;
KARP, RM .
JOURNAL OF THE ACM, 1972, 19 (02) :248-&
[6]  
GABOW HN, 1985, J COMPUT SYST SCI, V31, P148, DOI 10.1016/0022-0000(85)90039-X
[7]  
Gazit H., 1986, 27th Annual Symposium on Foundations of Computer Science (Cat. No.86CH2354-9), P492, DOI 10.1109/SFCS.1986.9
[8]  
GOLDBERG AV, 1988, 20TH P ACM S THEOR C, P388
[9]  
GOLDBERG AV, 1987, 19TH P ANN ACM S THE, P315
[10]  
KARP R, 1988, UCBCSD88408 U CAL CO
12