Enhanced Approximation Algorithms for Maximum Weight Matchings of Graphs
スポンサーリンク
概要
- 論文の詳細を見る
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 post-processings that consist of improved search of weight augmenting paths. Their performance is evaluated through results of computing experiment.
- (社)電子情報通信学会の論文
- 2008-04-01
著者
-
TAOKA Satoshi
Graduate School of Engineering, Hiroshima University
-
WATANABE Toshimasa
Graduate School of Engineering, Hiroshima University
-
Taoka Satoshi
Graduate School Of Engineering Hiroshima University
-
Taoka Satoshi
Hiroshima Univ. Higashihiroshima‐shi Jpn
-
Watanabe Toshimasa
Graduate School Of Engineering Hiroshima University
-
TAKAFUJI Daisuke
Graduate School of Engineering, Hiroshima University
-
NISHIKAWA Yasunori
Graduate School of Engineering, Hiroshima University
-
Watanabe Toshimasa
Hiroshima Univ. Higashi‐hiroshima Jpn
-
Takafuji Daisuke
Graduate School Of Engineering Hiroshima University
-
Nishikawa Yasunori
Graduate School Of Engineering Hiroshima University
-
Watanabe Toshimasa
Graduate School Of Engineering Hiroshima Univ.
関連論文
- Time Complexity Analysis of the Legal Firing Sequence Problem of Petri Nets with Inhibitor Arcs(Concurrent Systems,Concurrent/Hybrid Systems: Theory and Applications)
- A Fast Algorithm for (σ+1)-Edge-Connectivity Augmentation of a σ-Edge-Connected Graph with Multipartition Constraints
- A 2-Approximation Algorithm 2-ABIS for 2-Vertex-Connectivity Augmentation of Specified Vertices in a Graph
- A (2 - 2/|L|)-Approximation Algorithm R2VS or R2ES to 2-Vertex- or 2-Edge-Connect Specified Vertices in a Graph
- Efficiently Computing Minimal-Support Nonnegative Integer Invariants of Petri Nets
- Two Enhanced Heuristic Algorithms for the Minimum Initial Marking Problem of Petri Nets
- Improved Heuristic Algorithms for Minimizing Initial Markings of Petri Nets(Concurrent/Hybrid Systems : Theory and Applications)
- Experimental Evaluation of Two Algorithms for Computing Petri Net Invariants(Special Section on Concurrent Systems Technology)
- Enhancing PC Cluster-Based Parallel Branch-and-Bound Algorithms for the Graph Coloring Problem
- Enhanced Approximation Algorithms for Maximum Weight Matchings of Graphs
- Performance Comparison of Algorithms for the Dynamic Shortest Path Problem(Selected Papers from the 19th Workshop on Circuits and Systems in Karuizawa)
- Performance comparison of algorithms for the dynamic shortest path problem (グラフアルゴリスム)
- Finding Minimal Siphons in General Petri Nets (Special Section on Description Models for Concurrent Systems and Their Applications)
- A linear time algorithm for tri-connectivity augmentation of bi-connected graphs with upper bounds on vertex-degree increase (第21回 回路とシステム軽井沢ワークショップ論文集) -- (グラフアルゴリズム)
- On Minimum k-Edge-Connectivity Augmentation for Specified Vertices of a Graph with Upper Bounds on Vertex-Degree(Selected Papers from the 18th Workshop on Circuits and Systems in Karuizawa)
- Bi-Connectivity Augmentation for Specified Vertices of a Graph with Upper Bounds on Vertex-Degree Increase(Graph Algorithm, Foundations of Computer Science)
- A 2-Approximation Algorithm to (k+1)-Edge-Connect a Specified Set of Vertices in a k-Edge-Connected Graph(Discrete Mathematics and Its Applications)
- A Linear Time Algorithm for Bi-Connectivity Augmentation of Graphs with Upper Bounds on Vertex-Degree Increase(Selected Papers from the 17th Workshop on Circuits and Systems in Karuizawa)
- Extracting Minimal Siphon-Traps of Petri Nets and Its Application to Computing Nonnegative Integer-Invariants(Special Section on Concurrent System Technology and Its Application to Multiple Agent Systems)
- Experimental Evaluation of Maximum-Supply Partitioning Algorithms for Demand-Supply Graphs(Selected Papers from the 18th Workshop on Circuits and Systems in Karuizawa)
- Siphon-Trap-Based Algorithms for Efficiently Computing Petri Net Invariants(Selected Papers from the 17th Workshop on Circuits and Systems in Karuizawa)
- FOREWORD (Special Section on Discrete Mathematics and Its Applications)
- Tri-connectivity augmentation problems for bi-connected graphs with upper bounds on vertex-degree increase (ネツトワークの信頼性)
- FOREWORD
- The Marking Construction Problem of Petri Nets and Its Heuristic Algorithms
- A Fast Algorithm for Augmenting Edge-Connectivity by One with Bipartition Constraints
- Computing-Based Performance Analysis of Approximation Algorithms for the Minimum Weight Vertex Cover Problem of Graphs
- Two Heuristic Algorithms for the Minimum Initial Marking Problem of Timed Petri Nets