| 講演名 | 2000/1/19 次数増加禁止点を持つグラフの指定点集合に対する2, 3点連結化問題の解法 間島 利也, 渡邊 敏正, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 次数増加禁止点を持つグラフの指定点集合に対するk点連結化問題kVCA(G, S, D)は次のように定義される:"正整数k, 無向グラフG=(V, E), 指定点集合S⊆V, 次数増加可能点集合D⊆Vが与えられたときに, (V, E∪E')におけるSの点連結度がk以上であるような最小本数の辺集合E'⊆{(u, v)|u, v∈D}を求めよ."ここで, GにおけるSの点連結度とは, Gから除去するとSの点を含む連結成分数が2以上となるか又はSの点が1点だけとなるような, 点集合の最小点数である.V-Dの点をGの次数増加禁止点と呼ぶ.本稿では, 2VCA(G, S, D)又は3VCA(G, S, D)に対して, 解の存在性判定と解を求めることがそれぞれ, O(|V|+|E|)又はO(|V|(|V|+|E|))時間で実行できることを示す.( |
| 抄録(英) | The k-vertex-connectivity augmentation problem for a specified set of vertices of a graph with degree-unchangeable vertices, kVCA(G, S, D), is defined as follows: "Given a positive integer k, an undirected graph G=(V, E), a specified set of vertices S⊆V and a set of degree-changeable vertices D⊆V, find a smallest set of edges E' such that the vertex-connectivity of S in (V, E∪E') is at least k and E'⊆{(u, v)|u, v∈D}, where the vertex-connectivity of S in G is the minimum number of vetices whose deletion from G leaves either a graph that has at least two connected components each of which contains a vertex in S or a graph that contains only one vertex in S. " We call any vertex in V-D a degree-unchangeable vertex of G. In this paper, we show that, for 2VCA(G, S, D) or 3VCA(G, S, D), checking the existence of a solution and finding a solution to the problem can be done in O(|V|+|E|) or O(|V|(|V|+|E|)) time, respectively. |
| キーワード(和) | グラフアルゴリズム / 辺付加問題 / 点連結度 / 辺連結度 |
| キーワード(英) | graph algorithms / augmentation problems / vertex-connectivity / edge-connectivity |
| 資料番号 | COMP99-77 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2000/1/19(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 次数増加禁止点を持つグラフの指定点集合に対する2, 3点連結化問題の解法 |
| サブタイトル（和） | |
| タイトル（英） | Solving the 2-, 3-Vertex-Connectivity Augmentation Problem for Specified Vertices of a Graph with Degree-Unchangeable Ones |
| サブタイトル（和） | |
| キーワード(1)（和/英） | グラフアルゴリズム / graph algorithms |
| キーワード(2)（和/英） | 辺付加問題 / augmentation problems |
| キーワード(3)（和/英） | 点連結度 / vertex-connectivity |
| キーワード(4)（和/英） | 辺連結度 / edge-connectivity |
| 第 1 著者 氏名（和/英） | 間島 利也 / Toshiya Mashima |
| 第 1 著者 所属（和/英） | 広島市立大学情報科学部情報工学科 Department of Computer Engineering, Faculty of Information Sciences, Hirosima City University |
| 第 2 著者 氏名（和/英） | 渡邊 敏正 / Toshimasa Watanabe |
| 第 2 著者 所属（和/英） | 広島大学工学部第二類回路システム工学講座 Department of Circuits and Systems, Faculty of Engineering, Hiroshima University |
| 発表年月日 | 2000/1/19 |
| 資料番号 | COMP99-77 |
| 巻番号（vol） | vol.99 |
| 号番号（no） | 549 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |