| 講演名 | 2007-01-30 グラフの2点または3点連結化アルゴリズムの計算機実験に基づく性能評価 住吉 広春, 高藤 大介, 田岡 智志, 渡邉 敏正, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | グラフのk点連結化問題(kVCA)とは,「無向グラフG=(V,E), Gの部分グラフG_0=(V,E'),コスト関数c:E→Z^+(非負整数)が与えられたとき,G_0+E"がVの任意の異なる2点間にk本以上の内素なパスを持つようなコスト総和最小の付加辺集合E"⫋E-E'を求めよ.」と定義される.この問題は,通信網をはじめとするネットワーク設計等への応用を持つが,NP完全であることが知られており,近似解法または発見的解法が提案されている.本稿では,2VCAおよび3VCAに対する高精度な発見的解法を提案し、計算機実験によりそれらの性能評価を行う. |
| 抄録(英) | The k-vertex-connectivity augmentation problem (kVCA, for short) is defined by "Given a graph G=(V, E), a spanning subgraph G_0=(V, E') of G and a nonnegative weight function c:E→Z^+, find a set E"⫋E-E' with the minimum total weight, such that G_0+E"=(V, E'∪E") has at least k internally disjoint paths between any pair of vertices in V." Although these problems have wide application, such as constructing networks, it is known to be NP-complete. So some approximation or heuristic algorithms have been proposed. In this paper, we propose heuristic algorithms for 2VCA or 3VCA, and evaluate them through computational experiments. |
| キーワード(和) | グラフ / 点連結度 / 辺付加問題 / 発見的解法 |
| キーワード(英) | Graphs / vertex-connectivity / augmentation problem / heuristic algorithms |
| 資料番号 | CAS2006-70 |
| 発行日 |
| 研究会情報 | |
| 研究会 | CAS |
|---|---|
| 開催期間 | 2007/1/23(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Circuits and Systems (CAS) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | グラフの2点または3点連結化アルゴリズムの計算機実験に基づく性能評価 |
| サブタイトル（和） | |
| タイトル（英） | Experiment-based Evaluation of Algorithm Performance for the 2-or 3-Vertex Connectivity Augmentation Problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | グラフ / Graphs |
| キーワード(2)（和/英） | 点連結度 / vertex-connectivity |
| キーワード(3)（和/英） | 辺付加問題 / augmentation problem |
| キーワード(4)（和/英） | 発見的解法 / heuristic algorithms |
| 第 1 著者 氏名（和/英） | 住吉 広春 / Hiroharu SUMIYOSHI |
| 第 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 |
| 発表年月日 | 2007-01-30 |
| 資料番号 | CAS2006-70 |
| 巻番号（vol） | vol.106 |
| 号番号（no） | 512 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |