| 講演名 | 2009-09-24 グラフの最大誘導木を抽出する発見的解法の点除去に基づく性能強化 吉田 浩之, 高藤 大介, 田岡 智志, 渡邉 敏正, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | グラフの最大誘導木抽出問題(以下,MAXIT)とは、「与えられたグラフにおける誘導部分グラフが木となる頂点集合のうちで,点数最大なものを求めよ.」と定義される.この問題はNP困難であることが知られており,発見的解法が既にいくつか提案されている.本稿では,その中で比較的解精度の良い点除去に基づく解法に着目する.除去点の選択ルールを種々改善することによって解の高精度化を図り,計算機実験によってそれらの効果を検証する. |
| 抄録(英) | The problem of extracting a maximum induced tree of a graph (MAXIT) asks for a vertex set of largest cardinality among those ones each of which induces a tree of a given graph. It is known that this problem is NP-hard, and several heuristic algorithms for MAXIT have already been proposed. In this paper, we focused on vertex-deletion-based heuristic algorithms. We propose improved strategies for choosing vertices to be deleted so that sharpness of solutions may be obtained, and compare their effects by means of results of computing experiment. |
| キーワード(和) | 誘導部分グラフ抽出 / 最大誘導木 / グラフの点除去 / 発見的解法 / アルゴリズムの評価 |
| キーワード(英) | Extraction of induced subgraphs / maximum induced trees / vertex deletion of graphs / heuristic algorithms / evaluation of algorithms |
| 資料番号 | CAS2009-24,NLP2009-60 |
| 発行日 |
| 研究会情報 | |
| 研究会 | NLP |
|---|---|
| 開催期間 | 2009/9/17(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Nonlinear Problems (NLP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | グラフの最大誘導木を抽出する発見的解法の点除去に基づく性能強化 |
| サブタイトル（和） | |
| タイトル（英） | Vertex-Deletion-based Enhancement of Heuristic Algorithms for Extracting a Maximum Induced Tree of a Graph |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 誘導部分グラフ抽出 / Extraction of induced subgraphs |
| キーワード(2)（和/英） | 最大誘導木 / maximum induced trees |
| キーワード(3)（和/英） | グラフの点除去 / vertex deletion of graphs |
| キーワード(4)（和/英） | 発見的解法 / heuristic algorithms |
| キーワード(5)（和/英） | アルゴリズムの評価 / evaluation of algorithms |
| 第 1 著者 氏名（和/英） | 吉田 浩之 / Hiroyuki YOSHIDA |
| 第 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 |
| 発表年月日 | 2009-09-24 |
| 資料番号 | CAS2009-24,NLP2009-60 |
| 巻番号（vol） | vol.109 |
| 号番号（no） | 200 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |