Approximating weighted matchings in parallel

被引：16

作者：

Hougardy, Stefan ^{[1
]}

Vinkemeier, Doratha E. ^{[1
]}

机构：

[1] Humboldt Univ, Inst Informat, D-10099 Berlin, Germany

来源：

INFORMATION PROCESSING LETTERS | 2006年 / 99卷 / 03期

关键词：

approximation algorithms; parallel algorithms; analysis of algorithms; graph algorithms; maximum weight matching;

D O I：

10.1016/j.ipl.2006.03.005

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We present an NC approximation algorithm for the weighted matching problem in graphs with an approximation ratio of (1- epsilon). This improves the previously best approximation ratio of (1/2 - epsilon) of an algorithm for this problem. (c) 2006 Elsevier B.V. All rights reserved.

引用

页码：119 / 123

页数：5

共 13 条

[1]

Drake DE, 2003, LECT NOTES COMPUT SC, V2764, P14

[2]

DRAKE DE, 2005, ACM T ALGORITHMS, V1, P107

[3] APPROXIMATING MATCHINGS IN PARALLEL [J].

FISCHER, T ;

GOLDBERG, AV ;

HAGLIN, DJ ;

PLOTKIN, S .

INFORMATION PROCESSING LETTERS, 1993, 46 (03) :115-118

[4] A NEW PARALLEL ALGORITHM FOR THE MAXIMAL INDEPENDENT SET PROBLEM [J].

GOLDBERG, M ;

SPENCER, T .

SIAM JOURNAL ON COMPUTING, 1989, 18 (02) :419-427

[5]

Jaja J., 1992, INTRO PARALLEL ALGOR

[6] A LAS-VEGAS RNC ALGORITHM FOR MAXIMUM MATCHING [J].

KARLOFF, HJ .

COMBINATORICA, 1986, 6 (04) :387-391

[7] CONSTRUCTING A PERFECT MATCHING IS IN RANDOM NC [J].

KARP, RM ;

UPFAL, E ;

WIGDERSON, A .

COMBINATORICA, 1986, 6 (01) :35-48

[8]

Micali S., 1980, 21st Annual Symposium on Foundations of Computer Science, P17

[9] MATCHING IS AS EASY AS MATRIX-INVERSION [J].

MULMULEY, K ;

VAZIRANI, UV ;

VAZIRANI, VV .

COMBINATORICA, 1987, 7 (01) :105-113

[10]

Rytter W., 1998, FAST PARALLEL ALGORI

← 1 2 →