講演抄録/キーワード |
講演名 |
2011-06-30 11:05
需要点,供給点,辺容量を持つ木の分割アルゴリズム ○川端真生・西関隆夫(関西学院大) COMP2011-17 |
抄録 |
(和) |
木T の点は供給点あるいは需要点であるとし,各供給点には供給量と呼ばれる正の数が割り当てられ,各需要点には需要量と呼ばれる正の数が割り当てられているとする.また,各辺には正の数である容量が割り当てられているとする.T から辺を除去することによって,T をいくつかの部分木に分割し,各部分木はちょうど1 つの供給点を持ち,その供給量がその部分木の需要量の合計以上であり,しかも各辺を流れるフローが辺容量以下であるようにしたい.分割問題とはT にこのような分割が存在するか判定する問題であり,最大分割問題とは分割問題の最大化版である.本文ではこれらの問題に対して3つのアルゴリズムを与える.1 つ目は分割問題を線形時間で解くアルゴリズムである.2 つ目は最大分割問題を擬多項式時間で解くアルゴリズムである.3 つ目は最大分割問題を解くFPTAS(Fully Polynomial-Time Approximation Scheme)である. |
(英) |
Let T be a given tree. Each vertex of T is either a supply vertex or a demand vertex, and is assigned a positive number, called the supply or demand. Each demand vertex v must be supplied an amount of ``power," equal to the demand of v, from exactly one supply vertex through edges in T. Each edge is assigned a positive number called the capacity. One wishes to partition T into subtrees by deleting edges from T so that each subtree contains exactly one supply vertex whose supply is no less than the sum of all demands in the subtree and the power flow through each edge is no more than capacity of the edge. The ``partition problem" is a decision problem to ask whether T has such a partition. The ``maximum partition problem" is an optimization version of the partition problem. In this paper, we give three algorithms for the problems. First is a linear-time algorithm for the partition problem. Second is a pseudo-polynomial-time algorithm for the maximum partition problem. Third is a fully polynomial-time approximation scheme (FPTAS) for the maximum partition problem. |
キーワード |
(和) |
木 / 分割問題 / 最大分割問題 / 需要点 / 供給点 / 辺容量 / アルゴリズム / 近似 |
(英) |
tree / partition problem / maximum partition problem / supply vertex / demand vertex / edge-capacity / algorithm / approximation |
文献情報 |
信学技報, vol. 111, no. 113, COMP2011-17, pp. 9-16, 2011年6月. |
資料番号 |
COMP2011-17 |
発行日 |
2011-06-23 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2011-17 |