講演名 | 2000/4/26 次数増加禁止点を持つグラフの指定点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の次数増加禁止点と呼ぶ.本稿では, 3VCA(G, S, D)に対して, 解の存在性判定と解を求めることがO(|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 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. In this paper, we show that checking the existence of a solution and finding a solution to 3VCA(G, S, D) can be done in O(|V|+|E|) time. |
キーワード(和) | グラフアルゴリズム / 辺付加問題 / 点連結度 |
キーワード(英) | graph algorithms / augmentation problems / vertex-connectivity |
資料番号 | COMP2000-3 |
発行日 |
研究会情報 | |
研究会 | COMP |
---|---|
開催期間 | 2000/4/26(から1日開催) |
開催地(和) | |
開催地(英) | |
テーマ(和) | |
テーマ(英) | |
委員長氏名(和) | |
委員長氏名(英) | |
副委員長氏名(和) | |
副委員長氏名(英) | |
幹事氏名(和) | |
幹事氏名(英) | |
幹事補佐氏名(和) | |
幹事補佐氏名(英) |
講演論文情報詳細 | |
申込み研究会 | Theoretical Foundations of Computing (COMP) |
---|---|
本文の言語 | JPN |
タイトル(和) | 次数増加禁止点を持つグラフの指定点3点連結化問題に対する線形時間アルゴリズム |
サブタイトル(和) | |
タイトル(英) | A Linear Time Algorithm for the 3-Vertex-Connectivity Augmentation Problem for Specified Vertices of a Graph with Degree-Unchangeable Ones |
サブタイトル(和) | |
キーワード(1)(和/英) | グラフアルゴリズム / graph algorithms |
キーワード(2)(和/英) | 辺付加問題 / augmentation problems |
キーワード(3)(和/英) | 点連結度 / vertex-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 |
発表年月日 | 2000/4/26 |
資料番号 | COMP2000-3 |
巻番号(vol) | vol.100 |
号番号(no) | 25 |
ページ範囲 | pp.- |
ページ数 | 8 |
発行日 |