| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2011-06-30 11:05 需要点，供給点，辺容量を持つ木の分割アルゴリズム ○川端真生・西関隆夫（関西学院大）  COMP2011-17 |
|
| 抄録 | （和） | 木T の点は供給点あるいは需要点であるとし，各供給点には供給量と呼ばれる正の数が割り当てられ，各需要点には需要量と呼ばれる正の数が割り当てられているとする．また，各辺には正の数である容量が割り当てられているとする．T から辺を除去することによって，T をいくつかの部分木に分割し，各部分木はちょうど1 つの供給点を持ち，その供給量がその部分木の需要量の合計以上であり，しかも各辺を流れるフローが辺容量以下であるようにしたい．分割問題とはT にこのような分割が存在するか判定する問題であり，最大分割問題とは分割問題の最大化版である．本文ではこれらの問題に対して３つのアルゴリズムを与える．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 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2011-06-30 - 2011-06-30 |
| 開催地（和） | 広島大学 |
| 開催地（英） | Hiroshima Univ. |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2011-06-COMP |
| 本文の言語 | 英語（日本語タイトルあり） |
| タイトル（和） | 需要点，供給点，辺容量を持つ木の分割アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | Partitioning Trees with Supply, Demand and Edge-Capacity |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 木 / tree |
| キーワード(2)（和/英） | 分割問題 / partition problem |
| キーワード(3)（和/英） | 最大分割問題 / maximum partition problem |
| キーワード(4)（和/英） | 需要点 / supply vertex |
| キーワード(5)（和/英） | 供給点 / demand vertex |
| キーワード(6)（和/英） | 辺容量 / edge-capacity |
| キーワード(7)（和/英） | アルゴリズム / algorithm |
| キーワード(8)（和/英） | 近似 / approximation |
| 第1著者 氏名（和/英/ヨミ） | 川端 真生 / Masaki Kawabata / カワバタ マサキ |
| 第1著者 所属（和/英） | 関西学院大学 (略称： 関西学院大) Kwansei Gakuin University (略称： Kwansei Gakuin Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 西関 隆夫 / Takao Nishizeki / |
| 第2著者 所属（和/英） | 関西学院大学 (略称： 関西学院大) Kwansei Gakuin University (略称： Kwansei Gakuin Univ.) |
| 第3著者 氏名（和/英/ヨミ） | / / |
| 第3著者 所属（和/英） | (略称： ) (略称： ) |
| 第4著者 氏名（和/英/ヨミ） | / / |
| 第4著者 所属（和/英） | (略称： ) (略称： ) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2011-06-30 11:05:00 |
| 発表時間 | 35分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2011-17 |
| 巻番号（vol） | vol.111 |
| 号番号（no） | no.113 |
| ページ範囲 | pp.9-16 |
| ページ数 | 8 |
| 発行日 | 2011-06-23 (COMP) |
[研究会発表申込システムのトップページに戻る]