| 講演名 | 2008-10-10 木の均一分割問題 伊藤 健洋, 宇野 毅明, 周 暁, 西関 隆夫, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | グラフGの各点には非負整数の重みが割当てられているとし,lとuを0≦l≦uなる整数とする.このとき,Gから何本か辺を取り除いて,Gをいくつかの連結成分に分割したい.ただし,各連結成分に含まれる点重みの合計がl以上u以下でなければならない.このような分割を(l,u)の分割と呼ぶ.本論文では,与えられたグラフの(l,u)分割を見つける次の3つの問題を扱う.最少分割問題とは,最少の連結成分を持つ(l,u)分割を見つける問題である.最大分割問題は同様に定義される.p分割問題は,与えられた整数pに対し,ちょうどp個の連結成分を持つ(l,u)分割を見つける問題である.これら3つの問題は,直並列グラフに対してさえNP困難であるが,道に対しては線形時間で解け,木に対しては多項式時間で解ける.本論文では,木に対するこれら3つの問題を多項式時間で解くアルゴリズムを与える.我々のアルゴリズムは,従来知られているアルゴリズムよりも簡潔で高速である. |
| 抄録(英) | Assume that each vertex of a graph G is assigned a nonnegative integer weight and that l and u are integers such that 0≦l≦u. One wishes to partition G into connected components by deleting edges from G so that the total weight of each component is at least l and at most u. Such an "almost uniform" partition is called an (l, u)-partition. We deal with three problems to find an (l, u)-partition of a given graph: the minimum partition problem is to find an (l, u)-partition with the minimum number of components; the maximum partition problem is defined analogously; and the p-partition problem is to find an (l, u)-partition with a given number p of components. All these problems are NP-hard even for series-parallel graphs, but are solvable for paths in linear time and for trees in polynomial time. In this paper, we give polynomial-time algorithms to solve the three problems for trees, which are much simpler and faster than the known algorithms. |
| キーワード(和) | アルゴリズム / 下限 / 木 / 均一分割 / グラフ分割問題 / 上限 |
| キーワード(英) | algorithm / graph partition problem / lower bound / tree / uniform partition / upper bound |
| 資料番号 | COMP2008-41 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2008/10/3(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 木の均一分割問題 |
| サブタイトル（和） | |
| タイトル（英） | Partitioning a Weighted Tree to Subtrees of Almost Uniform Size |
| サブタイトル（和） | |
| キーワード(1)（和/英） | アルゴリズム / algorithm |
| キーワード(2)（和/英） | 下限 / graph partition problem |
| キーワード(3)（和/英） | 木 / lower bound |
| キーワード(4)（和/英） | 均一分割 / tree |
| キーワード(5)（和/英） | グラフ分割問題 / uniform partition |
| キーワード(6)（和/英） | 上限 / upper bound |
| 第 1 著者 氏名（和/英） | 伊藤 健洋 / Takehiro ITO |
| 第 1 著者 所属（和/英） | 東北大学大学院情報科学研究科 Graduate School of Information Sciences, Tohoku University |
| 第 2 著者 氏名（和/英） | 宇野 毅明 / Takeaki UNO |
| 第 2 著者 所属（和/英） | 国立情報学研究所 National Institute of Informatics |
| 第 3 著者 氏名（和/英） | 周 暁 / Xiao ZHOU |
| 第 3 著者 所属（和/英） | 東北大学大学院情報科学研究科 Graduate School of Information Sciences, Tohoku University |
| 第 4 著者 氏名（和/英） | 西関 隆夫 / Takao NISHIZEKI |
| 第 4 著者 所属（和/英） | 東北大学大学院情報科学研究科 Graduate School of Information Sciences, Tohoku University |
| 発表年月日 | 2008-10-10 |
| 資料番号 | COMP2008-41 |
| 巻番号（vol） | vol.108 |
| 号番号（no） | 237 |
| ページ範囲 | pp.- |
| ページ数 | 7 |
| 発行日 | |