APPROXIMATING MATCHINGS IN PARALLEL

被引：17
作者：
FISCHER, T
GOLDBERG, AV
HAGLIN, DJ
PLOTKIN, S
机构：
[1] STANFORD UNIV,DEPT COMP SCI,STANFORD,CA 94305
[2] CORNELL UNIV,DEPT COMP SCI,ITHACA,NY 14853
[3] MANKATO STATE UNIV,DEPT COMP & INFORMAT SCI,MANKATO,MN 56002
来源：
INFORMATION PROCESSING LETTERS | 1993年 / 46卷 / 03期
基金：
美国国家科学基金会;
关键词：
GRAPH MATCHING; PARALLEL ALGORITHMS; APPROXIMATION ALGORITHMS;
D O I：
10.1016/0020-0190(93)90055-E
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We show that for any constant k > 0, a matching with cardinality at least 1-1/(k+1) times the maximum can be computed in NC. © 1993.
引用
收藏
页码：115 / 118
页数：4
相关论文
共 15 条
[1]  
AGGARWAL A, 1987, 19TH P ANN ACM S THE, P325
[2]  
[Anonymous], 1983, DATA STRUCTURES NETW, DOI DOI 10.1137/1.9781611970265
[3]  
Cole R., 1986, 27th Annual Symposium on Foundations of Computer Science (Cat. No.86CH2354-9), P511, DOI 10.1109/SFCS.1986.41
[4]  
Goldberg A. V., 1988, 29th Annual Symposium on Foundations of Computer Science (IEEE Cat. No.88CH2652-6), P174, DOI 10.1109/SFCS.1988.21935
[5]  
GOLDBERG AV, 1989, STANCS891259 STANF U
[6]  
Goldberg M., 1989, SIAM J DISCRETE MATH, V2, P322
[7]  
HAGLIN DJ, 1989, THESIS U MINNESOTA
[8]  
Hopcroft J. E., 1973, SIAM Journal on Computing, V2, P225, DOI 10.1137/0202019
[9]  
Lawler E. L., 1976, COMBINATORIAL OPTIMI
[10]   A FAST PARALLEL ALGORITHM FOR ROUTING IN PERMUTATION NETWORKS [J].
LEV, GF ;
PIPPENGER, N ;
VALIANT, LG .
IEEE TRANSACTIONS ON COMPUTERS, 1981, 30 (02) :93-100
12