| 講演名 | 1998/4/24 グラフの付加辺多重度に上限を持つk-辺連結化問題 高藤 大介, 岡田 誠, 渡邊 敏正, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 各頂点間の付加辺数に上限を持つk-辺連結化問題を次のように定義する:"無向グラフG=(V, E)と関数f:V×V→Z^+^(非負整数)が与えられたとき, G′=(V, E∪E′)がk-辺連結であり, 且つ任意の2頂点u, vの間に付加された辺の本数がf(u, v)を越えないような辺集合E′の中で辺数が最小である辺集合を求めよ."本稿では, まずこの問題がNP-完全であることを示す.次に発見的解法を提案し, その能力を実験的に検証する. |
| 抄録(英) | The k-edge-connectivity augmentation problem of a graph with upper bounds on the multiplicity of added edges (kECA-UB, for short) is defined as follows : "Given a graph G = (V, E) and a function f : V × V → Z^+^ (nonnegative integers), find an edge set of minimum cardinality among those sets E′ such that G′ = (V, E∪E′) is k-edge connected and, for any two vertices u, v, the number of edges added between u and v is no more than f(u, v)." In this paper, we first show that this problem is NP-complete. Then we propose three heuristic algorithms for kECA-UB and compare their capability through experiment. |
| キーワード(和) | NP-完全問題 / 近似解法 / 解精度 |
| キーワード(英) | NP-completeness / approximation algorithms / performance ratios |
| 資料番号 | |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1998/4/24(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | グラフの付加辺多重度に上限を持つk-辺連結化問題 |
| サブタイトル（和） | |
| タイトル（英） | K-Edge-Connectivity Augmentation of a Graph with Upper Bounds on the Multiplicity of Added Edges |
| サブタイトル（和） | |
| キーワード(1)（和/英） | NP-完全問題 / NP-completeness |
| キーワード(2)（和/英） | 近似解法 / approximation algorithms |
| キーワード(3)（和/英） | 解精度 / performance ratios |
| 第 1 著者 氏名（和/英） | 高藤 大介 / Daisuke Takafuji |
| 第 1 著者 所属（和/英） | 広島大学大学院工学研究科情報工学専攻 Graduate School of Engineering, Hiroshima University |
| 第 2 著者 氏名（和/英） | 岡田 誠 / Makoto Okada |
| 第 2 著者 所属（和/英） | 広島大学工学部第二類回路システム工学講座 Department of Circuits and Systems, Faculty of Engineering, Hiroshima University |
| 第 3 著者 氏名（和/英） | 渡邊 敏正 / Toshimasa Watanabe |
| 第 3 著者 所属（和/英） | 広島大学工学部第二類回路システム工学講座 Department of Circuits and Systems, Faculty of Engineering, Hiroshima University |
| 発表年月日 | 1998/4/24 |
| 資料番号 | |
| 巻番号（vol） | vol.98 |
| 号番号（no） | 36 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |