支配集合問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』
支配集合問題（しはいしゅうごうもんだい）は、グラフ理論における有名なNP困難な問題の一つ。与えられたグラフ G(V,E) の頂点集合 V'(⊆V) で、V' に属さない全ての頂点 v について、v の隣接頂点のいずれか一つが V' に属するような V' （支配集合）のうち、最小のものを求める問題。
この問題は、集合被覆問題に含まれるため、集合被覆問題への近似アルゴリズムを適用することで近似度 1+log|V| の解を得ることができる。また、ある定数 c>0 について、c log|V| 近似アルゴリズムが存在しないことも示されている。
しかし、平面グラフに対しては、PTAS が存在することも知られている。
[編集] 関連項目
[編集] 外部リンク
- MINIMUM DOMINATING SET [1]
