Parallel approximation algorithms for maximum weighted matching in generalgraphs

The problem of computing a matching of maximum weight in a given edge-weigh ted graph is not known to be P-hard or in RNC. This paper presents two para llel approximation algorithms for this problem. The first is an RNC-approxi mation scheme, i.e., an RNC algorithm that computes a matching of weight at least 1 - epsilon times the maximum for any fixed constant epsilon > 0. Th e other is an NC approximation algorithm achieving an approximation ratio o f 1/(2 + epsilon) for any fixed constant epsilon > 0. (C) 2000 Elsevier Sci ence B.V. All rights reserved.