| 講演名 | 1999/12/10 次数増加禁止点を持つグラフに対する点連結度増加問題 間島 利也, 渡邉 敏正, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 次数増加禁止点を持つグラフの指定点集合に対するk点連結化問題kVCA (G, S, D)は次のように定義される:正整数k,無向グラフG = (V, E),指定点集合S ⫃ V,次数増加可能点集合D ⫃ Vが与えられたときに,(V, E⋃E^1)におけるSの点連結度がk以上であるような最小本数の辺集合E^1 ⫃ {(u, v)∣u, v ∈ D}を求めよ.ここで,GにおけるSの点連結度とは,Gから除去するとSの点を含む連結成分数が2以上となるか又はSの点が1点だけとなるような点集合の最小点数である.V - Dの点をGの次数増加禁止点と呼ぶ.kVCA (G, S, D), kVCA (G, V, D), kVCA (G, V, V), kVCA (G, S, S)をそれぞれk-SD, k-VD, k-VV, k-SSと表す.本稿では,まず(1) k-SDに解が存在するための必要十分条件を与える.次に(2) k-VDに対する解の存在性判定と解を求めることがk-VVの解法を用いることにより可能であること,及び(3) k <__- 3のときのk-SSがk-VDへの帰着により線形時間で解けることを示す. |
| 抄録(英) | 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^1 such that the vertex-connectivity of S in (V, E⋃E^1) is at least k and E^1 ⫃ {(u, v)∣u, v ∈ D}, where the vertex-connectivity of S in G is the minimum number of vertices 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. The problem kVCA (G, S, D), kVCA (G, V, D), kVCA (G, V, V) or kVCA (G, S, S) is denoted as k-SD, k-VD, k-VV or k-SS, respectively. In this paper, (1) we first give a necessary and sufficient condition for the existence of a solution to k-SD, and then we show that (2) checking the existence of a solution and finding a solution to k-VD can be done by using any algorithm for solving k-VV and that (3) k-SS for any k, k <__- 3, can be solved in linear time by reducing it to k-VD. |
| キーワード(和) | グラフアルゴリズム / 辺付加問題 / 点連結度 / 辺連結度 |
| キーワード(英) | graph algorithms / augmentation problems / vertex-connectivity / edge-connectivity |
| 資料番号 | COMP99-61 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1999/12/10(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 次数増加禁止点を持つグラフに対する点連結度増加問題 |
| サブタイトル（和） | |
| タイトル（英） | Vertex-Connectivity Augmentation Problems for Graphs with Degree-Unchangeable Vertices |
| サブタイトル（和） | |
| キーワード(1)（和/英） | グラフアルゴリズム / graph algorithms |
| キーワード(2)（和/英） | 辺付加問題 / augmentation problems |
| キーワード(3)（和/英） | 点連結度 / vertex-connectivity |
| キーワード(4)（和/英） | 辺連結度 / edge-connectivity |
| 第 1 著者 氏名（和/英） | 間島 利也 / Toshiya Mashima |
| 第 1 著者 所属（和/英） | 広島市立大学情報科学部情報工学科 Department of Computer Engineering, Faculty of Information Sciences, Hiroshima City University |
| 第 2 著者 氏名（和/英） | 渡邉 敏正 / Toshimasa Watanabe |
| 第 2 著者 所属（和/英） | 広島大学工学部第二類回路システム工学講座 Department of Circuits and Systems, Faculty of Engineering, Hiroshima University |
| 発表年月日 | 1999/12/10 |
| 資料番号 | COMP99-61 |
| 巻番号（vol） | vol.99 |
| 号番号（no） | 492 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |