| 講演抄録／キーワード |
| 講演名 |
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ダウンロード |
|