| 講演名 | 1995/9/22 無向グラフにおけるk-辺分割問題の一般化について 永持 仁, 石井 利昌, 茨木 俊秀, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | G=(V,E)を無向グラフとする.指定辺付k-辺分割問題は,Gのk本の辺e_1,…,e_kおよび辺数|E|のk個の正整数への分割m_1+…+m_k=|E|が与えられたとき,次の(1)(2)を満たすEの分割E_1∪…∪E_kを求める問題である.(1)e_1∈E_i,|E_i|=m_i(i=1,…,k,(2)各E_iに誘導される部分グラフが連結になる.Gがk-辺連結ならば,(1)(2)を満たす分割が必ず存在することが知られているが,分割を具体的に多項式時間で求めるアルゴリズムはk≤3の場合にのみ知られており,k>4については未解決である.本報告では,より一般化したラベル指定k-辺分割問題を導入する.すなわち,Gの各点に{1,…,k}から選んだラベルを自由に付したグラフ,および辺数の分割m_1+…+m_k=|E|に対し,次の(i)-(ii)の条件を満たす辺集合Eの分割E_1,…,E_kを求める問題である.(i)|E_i|=m_i(i=1,…,k),(ii)各E_iの誘導するグラフの各連結成分はラベルiのついた点を少なくとも1個含む.本報告では,k=2,3の場合について,この問題の分割が存在する十分条件を与え,この条件の下で分割を見つけるO(|E|)時間(k=2の場合)および,O(|E|+|V|^2)時間(k=3の場合)の多項式時間アルゴリズムを構築する. |
| 抄録(英) | Given an undirected graph G=(V, E) with k distinct edges e_i∈E(i=1,…,k), and natural numbers m_i(i=1,…,k) such that m_1+…+m_k=|E|, the k-edge-partition problem with specified bases asks to find a partition E_1…∪E_k of E such that (1)e_i∈E_i, and |E_i|=m_i(i=1,…,k), (2)each E_i induces a connected subgraph. It has been shown that there exists such a partition E_1∪…∪E_k if G is k-edge-connected. If the input graph is k-edge-connected, polynomial time algorithms for solving this problem are known for k=2,3, but no polynomial time algorithm is known for k≥4. In this paper, we generalize the probrem as follows. Given an undirected graph G=(V,E), where each vertex has some labels chosen from a label set {1,…,k}, and natural numbers m_i(i=1,…,k) such that m_1+…+m_k=|E|, the k-edge-partition problem with specified labels asks to find a partition E_1∪…∪E_k of E such that (i)|E_i|= m_i, and (ii) each connected component induced by E_i contains a vertex which has label i. We present a sufficient condition for this problem with k=2,3 to have such a partition, and construct O(|E|) and O(|E|+|V|^2) time algorithms for finding a partition under the condition for k=2 and 3, respectively. And we show that this problem can be solved in O(|E|)(k=2), O(|E|+|V|^2)(k=3) time. |
| キーワード(和) | k-辺連結グラフ / 指定辺付k-辺分割問題 / ラベル付きグラフ / ラベル指定k-辺分割問題 |
| キーワード(英) | k-edge-connected graph / k-edge-partition problem with specified bases / graph with specified labels / k-edge-partition problem with specified labels |
| 資料番号 | COMP95-46 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1995/9/22(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 無向グラフにおけるk-辺分割問題の一般化について |
| サブタイトル（和） | |
| タイトル（英） | Generalized k-edge-partition problem with specified bases |
| サブタイトル（和） | |
| キーワード(1)（和/英） | k-辺連結グラフ / k-edge-connected graph |
| キーワード(2)（和/英） | 指定辺付k-辺分割問題 / k-edge-partition problem with specified bases |
| キーワード(3)（和/英） | ラベル付きグラフ / graph with specified labels |
| キーワード(4)（和/英） | ラベル指定k-辺分割問題 / k-edge-partition problem with specified labels |
| 第 1 著者 氏名（和/英） | 永持 仁 / Hiroshi NAGAMOCHI |
| 第 1 著者 所属（和/英） | 京都大学 工学部 数理工学教室 Department of Applied Mathematics and Physics, Graduate School of Engineering, Kyoto University |
| 第 2 著者 氏名（和/英） | 石井 利昌 / Toshimasa ISHII |
| 第 2 著者 所属（和/英） | 京都大学 工学部 数理工学教室 Department of Applied Mathematics and Physics, Graduate School of Engineering, Kyoto University |
| 第 3 著者 氏名（和/英） | 茨木 俊秀 / Toshihide IBARAKI |
| 第 3 著者 所属（和/英） | 京都大学 工学部 数理工学教室 Department of Applied Mathematics and Physics, Graduate School of Engineering, Kyoto University |
| 発表年月日 | 1995/9/22 |
| 資料番号 | COMP95-46 |
| 巻番号（vol） | vol.95 |
| 号番号（no） | 259 |
| ページ範囲 | pp.- |
| ページ数 | 10 |
| 発行日 | |