| 講演名 | 1998/4/24 平面的グラフの基無指定k-分割問題に対する線形時間アルゴリズム 和田 幸一, 陳 慰, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | グラフのk-分割問題は、(1)無向グラフG=(V, E)、(2)V∪Eの部分集合S、(3)互いに異なるSのk個の要素a_i(1≤i≤k)、(4)Σ^k_ |
| 抄録(英) | This paper describes linear algorithms for partitioning a planar graph into k edge-disjoint connected subgraphs, each of which has a specified number of vertices and edges. If l(≤k) subgraphs contain the specified elements (called bases), we call this problem the k-partition problem with l-base (denoted by k-PART-B(l)). In this paper, we obtain the following results : (1)for any k ≥ 2, k-PART-B(1) can be solved in O(|E|) time for every 4-edge-connected planar graph G=(V, E), (2) 3-PART-B(1) can be solved in O(|E|) time for every 2-edge-connected planar graph G=(V, E) and (3) 5-PART-B(1) can be solved in O(|E|) time for every 3-edge-connected planar graph G=(V, E). |
| キーワード(和) | k-辺連結平面的グラフ / 辺分割 / オイラーサイクル / 標準順序 / 3連結成分 |
| キーワード(英) | k-edge-connected planar graph / edge partition / Eulerian cycle / canonical ordering / triconnected components |
| 資料番号 | |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1998/4/24(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 平面的グラフの基無指定k-分割問題に対する線形時間アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | Linear Algorithms for a k-partition Problem of Planar Graphs without Specifying Bases |
| サブタイトル（和） | |
| キーワード(1)（和/英） | k-辺連結平面的グラフ / k-edge-connected planar graph |
| キーワード(2)（和/英） | 辺分割 / edge partition |
| キーワード(3)（和/英） | オイラーサイクル / Eulerian cycle |
| キーワード(4)（和/英） | 標準順序 / canonical ordering |
| キーワード(5)（和/英） | 3連結成分 / triconnected components |
| 第 1 著者 氏名（和/英） | 和田 幸一 / Koichi Wada |
| 第 1 著者 所属（和/英） | 名古屋工業大学電気情報工学科 Nagoya Institute of Technology |
| 第 2 著者 氏名（和/英） | 陳 慰 / Wei Chen |
| 第 2 著者 所属（和/英） | 名古屋工業大学電気情報工学科 Nagoya Institute of Technology |
| 発表年月日 | 1998/4/24 |
| 資料番号 | |
| 巻番号（vol） | vol.98 |
| 号番号（no） | 36 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |