| 講演名 | 2010-12-03 需要点と供給点のある木のコスト最小分割 伊藤 健洋, 原 拓哉, 周 暁, 西関 隆夫, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 与えられた木Tの各点は供給点または需要点であり,それぞれ供給量または需要量と呼ばれる正整数が割当てられている.Tの各々の需要点vに対し,vの需要量に等しいパワーを,Tの向き付けされた辺を通して,1個の供給点からvに供給したい.Tの各辺eには向きと正整数が割当てられていて,この正整数はTからeを除去するか,あるいはeの向きを逆向きにするのにかかるコストを表している.このとき,Tから辺を除去したり,辺の向きを逆にしたりして,次の条件(a)と(b)を満たすようにTをいくつかの部分木に分割したい.(a)各部分木には,ちょうど1個の供給点があり,その供給量はその部分木に含まれる全ての需要点の需要量の合計以上である.(b)各部分木は供給点を根とした根付き木であり,全ての辺は親から子へ向き付けされている.本論文では,与えられた木Tをこのような根付き部分木に分割するためにかかるコストを最小化する問題を扱う.この最小化問題がNP困難であることを示した上で,この問題を解く擬多項式時間アルゴリズムを与える.更に,この問題に対する多項式時間の完全近似スキーム(FPTAS)も与える. |
| 抄録(英) | Let T be a given tree. Each vertex of T is either a supply vertex or a demand vertex, and is assigned a positive integer, called the supply or the demand. Every demand vertex v of T must be supplied an amount of "power," equal to the demand of v, from exactly one supply vertex through edges in T. Each edge e of T has a direction, and is assigned a positive integer which represents the cost required to delete e from T or reverse the direction of e. Then one wishes to obtain subtrees of T by deleting edges and reversing the directions of edges so that (a) each subtree contains exactly one supply vertex whose supply is no less than the sum of all demands in the subtree and (b) each subtree is rooted at the supply vertex in a sense that every edge is directed away from the root. We wish to minimize the total cost to obtain such rooted subtrees from T. In the paper, we first show that this minimization problem is NP-hard, and then give a pseudo-polynomial-time algorithm to solve the problem. We finally give a fully polynomial-time approximation scheme (FPTAS) for the problem. |
| キーワード(和) | 完全近似スキーム / 木 / 近似アルゴリズム / 供給点 / グラフ分割 / 需要点 / 有向辺 |
| キーワード(英) | approximation algorithm / demand vertex / directed edge / FPTAS / graph partition / supply vertex / tree |
| 資料番号 | COMP2010-44 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2010/11/26(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 需要点と供給点のある木のコスト最小分割 |
| サブタイトル（和） | |
| タイトル（英） | Minimum Cost Partitions of Trees with Supply and Demand |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 完全近似スキーム / approximation algorithm |
| キーワード(2)（和/英） | 木 / demand vertex |
| キーワード(3)（和/英） | 近似アルゴリズム / directed edge |
| キーワード(4)（和/英） | 供給点 / FPTAS |
| キーワード(5)（和/英） | グラフ分割 / graph partition |
| キーワード(6)（和/英） | 需要点 / supply vertex |
| キーワード(7)（和/英） | 有向辺 / tree |
| 第 1 著者 氏名（和/英） | 伊藤 健洋 / Takehiro ITO |
| 第 1 著者 所属（和/英） | 東北大学大学院情報科学研究科 Graduate School of Information Sciences, Tohoku University |
| 第 2 著者 氏名（和/英） | 原 拓哉 / Takuya HARA |
| 第 2 著者 所属（和/英） | 東北大学大学院情報科学研究科 Graduate School of Information Sciences, Tohoku University |
| 第 3 著者 氏名（和/英） | 周 暁 / Xiao ZHOU |
| 第 3 著者 所属（和/英） | 東北大学大学院情報科学研究科 Graduate School of Information Sciences, Tohoku University |
| 第 4 著者 氏名（和/英） | 西関 隆夫 / Takao NISHIZEKI |
| 第 4 著者 所属（和/英） | 関西学院大学理工学部 School of Science and Technology, Kwansei Gakuin University |
| 発表年月日 | 2010-12-03 |
| 資料番号 | COMP2010-44 |
| 巻番号（vol） | vol.110 |
| 号番号（no） | 325 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |