Parallel Approximation Algorithms for Maximum Weighted Matching in General Graphs

概要

論文の詳細を見る
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 1 - ε times the maximum for any given constant ε > 0. The second one is an NC approximation algorithm achieving an approximation ratio of 1/(2+ε) for any fixed ε > 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/(3Δ+2) times the maximum, where Δ is the maximum degree of the graph. The fourth one is an RNC algorithm that finds a matching of weight at least 1/(2Δ+4) times the maximum on average, and runs in Ο(log Δ) time, not depending on the size of the graph.
Springerの論文
2000-00-00