| 講演名 | 2006-11-20 グラフ最大重みマッチング問題に対する高速・高精度の近似解法 : 重み増加パス探索の改良による性能強化(グラフ,ペトリ,ニューラルネット及び一般) 西河 恭倫, 高藤 大介, 田岡 智志, 渡邉 敏正, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | グラフ最大重みマッチング問題とは,辺重みを持つグラフG=(V,E)において重み総和最大のマッチングを求める問題である.マッチングMとは,どの辺も互いに端点を共有しない辺集合M⊆Eである.最大重みマッチングの最適解を求める多項式時間解法がいくつか提案されているが,グラフサイズが大きくなると最適解を得るには極端に多くの計算時間を必要とする.そこで,実用性を考慮して高速な近似解法がいくつか提案されている.その中でも重み増加パスを利用した手法は,実験的に近似解法では解精度がよいという結果が得られている.本稿では,重み増加パス探索を利用した近似解法に着目し,それを改良した手法をいくつか提案し,計算機実験によりその性能を示す. |
| 抄録(英) | The maximum weight matching problem (MWM) is to find a maximum weight matching of a given graph G=(V,E). The term "a graph" means an edge-weighted undirected graph. An edge set M is called a matching if and only if any pair of edges in M share no endvertices. Polynominal algorithms for finding an optimum solution to MWM have already been proposed, but they require extremely long computation time as the size of a given graph becomes large. So, from practical points of view, several fast approximation algorithms have been proposed. It is known that approximation algorithms based on searching weighted augmenting paths show high capability in experimental-based evaluation. This paper focuses on such approximation algorithms and proposes several improved algorithms. This performance is compared through computational experiment. |
| キーワード(和) | グラフ最大重みマッチング / 近似解法 / 重み増加パス |
| キーワード(英) | the Maximum Weight Matching Problem of Graphs / approximate solutions / weight augmenting paths |
| 資料番号 | CAS2006-52,CST2006-28 |
| 発行日 |
| 研究会情報 | |
| 研究会 | CST |
|---|---|
| 開催期間 | 2006/11/13(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Concurrent System Technology (CST) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | グラフ最大重みマッチング問題に対する高速・高精度の近似解法 : 重み増加パス探索の改良による性能強化(グラフ,ペトリ,ニューラルネット及び一般) |
| サブタイトル（和） | |
| タイトル（英） | Fast and Sharp Approximation Algorithms for the Maximum Weight Matching Problem of Graphs : Enchancing by improved search of weight augmenting paths |
| サブタイトル（和） | |
| キーワード(1)（和/英） | グラフ最大重みマッチング / the Maximum Weight Matching Problem of Graphs |
| キーワード(2)（和/英） | 近似解法 / approximate solutions |
| キーワード(3)（和/英） | 重み増加パス / weight augmenting paths |
| 第 1 著者 氏名（和/英） | 西河 恭倫 / Yasunori NISHIKAWA |
| 第 1 著者 所属（和/英） | 広島大学大学院工学研究科情報工学専攻 Graduate School of Engineering, Hiroshima University |
| 第 2 著者 氏名（和/英） | 高藤 大介 / Daisuke TAKAFUJI |
| 第 2 著者 所属（和/英） | 広島大学大学院工学研究科情報工学専攻 Graduate School of Engineering, Hiroshima University |
| 第 3 著者 氏名（和/英） | 田岡 智志 / Satoshi TAOKA |
| 第 3 著者 所属（和/英） | 広島大学大学院工学研究科情報工学専攻 Graduate School of Engineering, Hiroshima University |
| 第 4 著者 氏名（和/英） | 渡邉 敏正 / Toshimasa WATANABE |
| 第 4 著者 所属（和/英） | 広島大学大学院工学研究科情報工学専攻 Graduate School of Engineering, Hiroshima University |
| 発表年月日 | 2006-11-20 |
| 資料番号 | CAS2006-52,CST2006-28 |
| 巻番号（vol） | vol.106 |
| 号番号（no） | 367 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |