Enhanced Approximation Algorithms for Maximum Weight Matchings of Graphs

Daisuke TAKAFUJI; Satoshi TAOKA; Yasunori NISHIKAWA; Toshimasa WATANABE

doi:10.1093/ietfec/e91-a.4.1129

Enhanced Approximation Algorithms for Maximum Weight Matchings of Graphs

Daisuke TAKAFUJI, Satoshi TAOKA, Yasunori NISHIKAWA, Toshimasa WATANABE

Full Text Views

0

Cite this

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|⁴) 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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E91-A No.4 pp.1129-1139

Publication Date: 2008/04/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1093/ietfec/e91-a.4.1129

Type of Manuscript: Special Section PAPER (Special Section on Selected Papers from the 20th Workshop on Circuits and Systems in Karuizawa)

Category

Cite this

Copy

Daisuke TAKAFUJI, Satoshi TAOKA, Yasunori NISHIKAWA, Toshimasa WATANABE, "Enhanced Approximation Algorithms for Maximum Weight Matchings of Graphs" in IEICE TRANSACTIONS on Fundamentals, vol. E91-A, no. 4, pp. 1129-1139, April 2008, doi: 10.1093/ietfec/e91-a.4.1129.
Abstract: 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|⁴) 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e91-a.4.1129/_p

Copy

@ARTICLE{e91-a_4_1129,
author={Daisuke TAKAFUJI, Satoshi TAOKA, Yasunori NISHIKAWA, Toshimasa WATANABE, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Enhanced Approximation Algorithms for Maximum Weight Matchings of Graphs},
year={2008},
volume={E91-A},
number={4},
pages={1129-1139},
abstract={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|⁴) 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.},
keywords={},
doi={10.1093/ietfec/e91-a.4.1129},
ISSN={1745-1337},
month={April},}

Copy

TY - JOUR
TI - Enhanced Approximation Algorithms for Maximum Weight Matchings of Graphs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1129
EP - 1139
AU - Daisuke TAKAFUJI
AU - Satoshi TAOKA
AU - Yasunori NISHIKAWA
AU - Toshimasa WATANABE
PY - 2008
DO - 10.1093/ietfec/e91-a.4.1129
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E91-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 2008
AB - 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|⁴) 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.
ER -