| 講演抄録／キーワード |
| 講演名 |
2006-10-17 10:25
Approximability of Partitioning Graphs with Supply and Demand
○Takehiro Ito（Tohoku Univ.）・Erik D.Demaine（MIT）・Xiao Zhou・Takao Nishizeki（Tohoku Univ.） |
| 抄録 |
（和） |
グラフ$G$の各点は需要点あるいは供給点であり，各々需要量や供給量と呼ばれる正の実数が割当てられているとし，各需要点は1個の供給点だけからグラフの辺を通して供給を受けることができるとする．したがって，$G$から何本か辺を取り除いて$G$をいくつかの連結成分に分割し，各連結成分には供給点がないか，あるいはちょうど1個だけあるようにしたい．ただし，供給点のある各連結成分においてはその供給量は連結成分にある需要点の需要量の合計以上でなければならない．このような分割で，供給点のある連結成分に含まれる需要点の需要量の合計を最大にする分割を求めたい．本文ではこのような最大化問題を扱う．この問題は，供給点が1点しかない木に対してさえNP困難であり，一般のグラフに対しては強NP困難である．本文では，この問題の近似可能性について考察する．まず，この問題はMAXSNP困難であることを示す．したがって，${\rm P}={\rm NP}$でない限りは，一般のグラフに対して多項式時間の近似スキーム(PTAS)が存在しない．次に，供給点がちょうど1個しかない直並列グラフに対しては，完全近似スキーム(FPTAS)が存在することを示す．なお，本文の完全近似スキームは，容易に部分$k$木に拡張することができる． |
| （英） |
Suppose that each vertex of a graph $G$ is either a supply vertex or a demand vertex and is assigned a positive real number, called the supply or the demand. Each demand vertex can receive ``power'' from at most one supply vertex through edges in $G$. One thus wishes to partition $G$ into connected components so that each component $C$ either has no supply vertex or has exactly one supply vertex whose supply is at least the sum of demands in $C$, and wishes to maximize the fulfillment, that is, the sum of demands in all components with supply vertices. This maximization problem is known to be NP-hard even for trees having exactly one supply vertex and strongly NP-hard for general graphs. In this paper, we focus on the approximability of the problem. We first show that the problem is MAXSNP-hard and hence there is no polynomial-time approximation scheme (PTAS) for general graphs unless ${\rm P}={\rm NP}$. We then present a fully polynomial-time approximation scheme (FPTAS) for series-parallel graphs having exactly one supply vertex. The FPTAS can be easily extended for partial $k$-trees, that is, graphs with bounded treewidth. |
| キーワード |
（和） |
近似アルゴリズム / 需要点 / 完全近似スキーム / 最大分割問題 / MAXSNP困難 / 部分$k$木 / 直並列グラフ / 供給点 |
| （英） |
approximation algorithm / demand / FPTAS / maximum partition problem / MAXSNP-hard / partial $k$-tree / series-parallel graph / supply |
| 文献情報 |
信学技報, vol. 106, no. 289, COMP2006-33, pp. 17-23, 2006年10月. |
| 資料番号 |
COMP2006-33 |
| 発行日 |
2006-10-10 (COMP) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|
| 研究会情報 |
| 研究会 |
COMP |
| 開催期間 |
2006-10-17 - 2006-10-17 |
| 開催地（和） |
東北大学 |
| 開催地（英） |
Tohoku University |
| テーマ（和） |
|
| テーマ（英） |
|
| 講演論文情報の詳細 |
| 申込み研究会 |
COMP |
| 会議コード |
2006-10-COMP |
| 本文の言語 |
英語 |
| タイトル（和） |
|
| サブタイトル（和） |
|
| タイトル（英） |
Approximability of Partitioning Graphs with Supply and Demand |
| サブタイトル（英） |
|
| キーワード(1)（和/英） |
近似アルゴリズム / approximation algorithm |
| キーワード(2)（和/英） |
需要点 / demand |
| キーワード(3)（和/英） |
完全近似スキーム / FPTAS |
| キーワード(4)（和/英） |
最大分割問題 / maximum partition problem |
| キーワード(5)（和/英） |
MAXSNP困難 / MAXSNP-hard |
| キーワード(6)（和/英） |
部分$k$木 / partial $k$-tree |
| キーワード(7)（和/英） |
直並列グラフ / series-parallel graph |
| キーワード(8)（和/英） |
供給点 / supply |
| 第1著者 氏名（和/英/ヨミ） |
伊藤 健洋 / Takehiro Ito / イトウ タケヒロ |
| 第1著者 所属（和/英） |
東北大学 (略称： 東北大)
Tohoku University (略称： Tohoku Univ.) |
| 第2著者 氏名（和/英/ヨミ） |
Erik Demaine / Erik D.Demaine / Erik D.Demaine |
| 第2著者 所属（和/英） |
マサチューセッツ工科大学 (略称： マサチューセッツ工科大)
Massachusetts Institute of Technology (略称： MIT) |
| 第3著者 氏名（和/英/ヨミ） |
周 暁 / Xiao Zhou / シュウ ギョウ |
| 第3著者 所属（和/英） |
東北大学 (略称： 東北大)
Tohoku University (略称： Tohoku Univ.) |
| 第4著者 氏名（和/英/ヨミ） |
西関 隆夫 / Takao Nishizeki / ニシゼキ タカオ |
| 第4著者 所属（和/英） |
東北大学 (略称： 東北大)
Tohoku University (略称： Tohoku Univ.) |
| 第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著者 所属（和/英） |
(略称： )
(略称： ) |
| 第19著者 氏名（和/英/ヨミ） |
/ / |
| 第19著者 所属（和/英） |
(略称： )
(略称： ) |
| 第20著者 氏名（和/英/ヨミ） |
/ / |
| 第20著者 所属（和/英） |
(略称： )
(略称： ) |
| 第21著者 氏名（和/英/ヨミ） |
/ / |
| 第21著者 所属（和/英） |
(略称： )
(略称： ) |
| 第22著者 氏名（和/英/ヨミ） |
/ / |
| 第22著者 所属（和/英） |
(略称： )
(略称： ) |
| 第23著者 氏名（和/英/ヨミ） |
/ / |
| 第23著者 所属（和/英） |
(略称： )
(略称： ) |
| 第24著者 氏名（和/英/ヨミ） |
/ / |
| 第24著者 所属（和/英） |
(略称： )
(略称： ) |
| 第25著者 氏名（和/英/ヨミ） |
/ / |
| 第25著者 所属（和/英） |
(略称： )
(略称： ) |
| 第26著者 氏名（和/英/ヨミ） |
/ / |
| 第26著者 所属（和/英） |
(略称： )
(略称： ) |
| 第27著者 氏名（和/英/ヨミ） |
/ / |
| 第27著者 所属（和/英） |
(略称： )
(略称： ) |
| 第28著者 氏名（和/英/ヨミ） |
/ / |
| 第28著者 所属（和/英） |
(略称： )
(略称： ) |
| 第29著者 氏名（和/英/ヨミ） |
/ / |
| 第29著者 所属（和/英） |
(略称： )
(略称： ) |
| 第30著者 氏名（和/英/ヨミ） |
/ / |
| 第30著者 所属（和/英） |
(略称： )
(略称： ) |
| 第31著者 氏名（和/英/ヨミ） |
/ / |
| 第31著者 所属（和/英） |
(略称： )
(略称： ) |
| 第32著者 氏名（和/英/ヨミ） |
/ / |
| 第32著者 所属（和/英） |
(略称： )
(略称： ) |
| 第33著者 氏名（和/英/ヨミ） |
/ / |
| 第33著者 所属（和/英） |
(略称： )
(略称： ) |
| 第34著者 氏名（和/英/ヨミ） |
/ / |
| 第34著者 所属（和/英） |
(略称： )
(略称： ) |
| 第35著者 氏名（和/英/ヨミ） |
/ / |
| 第35著者 所属（和/英） |
(略称： )
(略称： ) |
| 第36著者 氏名（和/英/ヨミ） |
/ / |
| 第36著者 所属（和/英） |
(略称： )
(略称： ) |
| 講演者 |
第1著者 |
| 発表日時 |
2006-10-17 10:25:00 |
| 発表時間 |
35分 |
| 申込先研究会 |
COMP |
| 資料番号 |
COMP2006-33 |
| 巻番号（vol） |
vol.106 |
| 号番号（no） |
no.289 |
| ページ範囲 |
pp.17-23 |
| ページ数 |
7 |
| 発行日 |
2006-10-10 (COMP) |