支配集合問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』
2013年3月25日 (月) 00:31時点におけるAddbot (トーク)による版 (ボット: 言語間リンク 5 件をウィキデータ上の d:q2915204 に転記)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先: 案内検索

支配集合問題(しはいしゅうごうもんだい)は、グラフ理論における有名なNP困難な問題の一つ。与えられたグラフ G(V, E) の頂点集合 V′ (⊆ V) で、V′ に属さない全ての頂点 v について、v の隣接頂点のいずれか一つが V′ に属するような V′ (支配集合)のうち、最小のものを求める問題。

この問題は、集合被覆問題に含まれるため、集合被覆問題への近似アルゴリズムを適用することで近似度 1 + log|V| の解を得ることができる。また、ある定数 c > 0 について、c log|V| 近似アルゴリズムが存在しないことも示されている。

しかし、平面グラフに対しては、PTAS が存在することも知られている。

関連項目

外部リンク