The search functionality is under construction.
The search functionality is under construction.

Keyword Search Result

[Keyword] approximate solutions(1hit)

1-1hit
  • Enhanced Approximation Algorithms for Maximum Weight Matchings of Graphs

    Daisuke TAKAFUJI  Satoshi TAOKA  Yasunori NISHIKAWA  Toshimasa WATANABE  

     
    PAPER

      Vol:
    E91-A No:4
      Page(s):
    1129-1139

    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.