支配数問題の近似アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
グラフの支配数問題とは,頂点集合をできるだけ多くの,互いに素な支配集合に分割する問題である.本稿では,グラフの頂点数をn,最小次数をδとしたとき,任意のグラフがサイズ(1-o(1))(δ+1)/ln nの分割を持つことを構成的証明により示す.つまり,近似度(1+o(1))ln n,の近似アルゴリズムを構成したことになる.さらに本稿では,この近似度は本質的に最適であることを示す.すなわち,任意のε>0に対して,(1-ε)ln n-近似アルゴリズムが存在すればNP⊆TIME(n^<lglgn>)となることを示す.従って,本論文は,(ln n)^<0(1)>では近似できるが,それよりも良い近似アルゴリズムはおそらく存在しないと強く予想できる,自然な最大化問題を初めて示したことになる.
- 1999-11-16