|
Abstract : |
Abstract. The problem of computing a matching of maximum weight in a given edge-weighted graph is not known to be P-hard or in RNC. This paper presents four parallel approximation algorithms for this problem. The first is an RNC-approximation scheme, i.e., an RNC algorithm that computes a matching of weight at least 10 ffl times the maximum for any given constant ffl? 0. The second one is an NC approximation algorithm achieving an approximation ratio of 1 2+ffl for any fixed ffl? 0. The third and fourth algorithms only need to know the total order of weights, so they are useful when the edge weights require a large amount of memories to represent. The third one is an NC approximation algorithm that finds a matching of weight at least 2 31+2 times the maximum, where 1 is the maximum degree of the graph. The fourth one is an RNC algorithm that finds a matching of weight at least 1 21+4 times the maximum on average, and runs in O(log 1) time, not depending on the size of the graph. Key words: Graph algorithm, maximum weighted matching, approximation, |
