Enhanced Approximation Algorithms for Maximum Weight Matchings of Graphs

Daisuke TAKAFUJI  Satoshi TAOKA  Yasunori NISHIKAWA  Toshimasa WATANABE 

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences  Vol.E91-A  No.4  pp.1129-1139
Publication Date: 2008/04/01
Online ISSN: 1745-1337
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Selected Papers from the 20th Workshop on Circuits and Systems in Karuizawa)
Category: 
Keyword: 
the maximum weight matching problem of graphs,  approximate solutions,  weight augmenting paths, 

Full Text: PDF(490.7KB)

Summary: 
The subject of this paper is maximum weight matchings of graphs. An edge set M of a given graph G is called a matching if and only if any pair of edges in M share no endvertices. A maximum weight matching is a matching whose total weight (total sum of edge-weights) is maximum among those of G. The maximum weight matching problem (MWM for short) is to find a maximum weight matching of a given graph. Polynomial algorithms for finding an optimum solution to MWM have already been proposed: for example, an O(|V|4) time algorithm proposed by J. Edmonds, and an O(|E||V|log |V|) time algorithm proposed by H.N. Gabow. Some applications require obtaining a matching of large total weight (not necessarily a maximum one) in realistic computing time. These existing algorithms, however, spend extremely long computing time as the size of a given graph becomes large, and several fast approximation algorithms for MWM have been proposed. In this paper, we propose six approximation algorithms GRS+, GRS_F+, GRS_R+, GRS_S+, LAM_a+ and LAM_as+. They are enhanced from known approximation ones by adding some postprocessings that consist of improved search of weight augmenting paths. Their performance is evaluated through results of computing experiment.