支配集合問題に対する近似アルゴリズム、についての問題です。

支配集合問題に対する近似アルゴリズム、についての問題です。

次の様な問題です。


「グラフ G=(V,E) に対し、支配集合を次のように定義する:

定義1 (支配集合). 頂点の部分集合 D⊆V は、Dに属さない全ての頂点に対して少なくとも1つのDに属する頂点が隣接するときに支配集合という。

与えられたグラフにおける大きさ最小の支配集合を見付ける問題を支配集合問題という。この問題に対する近似アルゴリズムを与え、そのアルゴリズムの近似率を求めよ。」


正直に言って、糸口さえ掴めず全く分かりません。
近似アルゴリズムに詳しい方、回答をよろしくお願いします。

No.1 ベストアンサー 回答者： R_Earl 回答日時： 2010/05/27 18:57

> 正直に言って、糸口さえ掴めず全く分かりません。

> 近似アルゴリズムに詳しい方、回答をよろしくお願いします。

Google等でキーワード「支配集合問題」で検索すると、
支配集合問題を解くアルゴリズムが見つかります。
いくつか方法があるようなので、まずどのアルゴリズムを使うかを決めましょう。
その上で近似率がどうなるかを考えてみてはいかがでしょうか。

この回答へのお礼

回答ありがとうございました。

お礼日時：2010/05/27 22:04