| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2008-10-10 14:30 木の均一分割問題 ○伊藤健洋（東北大）・宇野毅明（NII）・周 暁・西関隆夫（東北大）  COMP2008-41 |
|
| 抄録 | （和） | グラフ$G$の各点には非負整数の重みが割当てられているとし，$l$と$u$を$0 \le l \le 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 \le l \le 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 / / | |
| 文献情報 | 信学技報, vol. 108, no. 237, COMP2008-41, pp. 55-61, 2008年10月. | |
| 資料番号 | COMP2008-41 | |
| 発行日 | 2008-10-03 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2008-41 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2008-10-10 - 2008-10-10 |
| 開催地（和） | 東北大学 |
| 開催地（英） | Tohoku Univ. |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2008-10-COMP |
| 本文の言語 | 英語（日本語タイトルあり） |
| タイトル（和） | 木の均一分割問題 |
| サブタイトル（和） | |
| タイトル（英） | 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 |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 伊藤 健洋 / Takehiro Ito / イトウ タケヒロ |
| 第1著者 所属（和/英） | 東北大学 (略称： 東北大) Tohoku University (略称： Tohoku Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 宇野 毅明 / Takeaki Uno / ウノ タケアキ |
| 第2著者 所属（和/英） | 国立情報学研究所 (略称： NII) National Institute of Informatics (略称： NII) |
| 第3著者 氏名（和/英/ヨミ） | 周 暁 / Xiao Zhou / シュウ ギョウ |
| 第3著者 所属（和/英） | 東北大学 (略称： 東北大) Tohoku University (略称： Tohoku Univ.) |
| 第4著者 氏名（和/英/ヨミ） | 西関 隆夫 / Takao Nishizeki / ニシゼキ タカオ |
| 第4著者 所属（和/英） | 東北大学 (略称： 東北大) Tohoku University (略称： Tohoku Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2008-10-10 14:30:00 |
| 発表時間 | 30分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2008-41 |
| 巻番号（vol） | vol.108 |
| 号番号（no） | no.237 |
| ページ範囲 | pp.55-61 |
| ページ数 | 7 |
| 発行日 | 2008-10-03 (COMP) |
[研究会発表申込システムのトップページに戻る]