三角形を含まない3-正則グラフの最大独立点集合を求める近似アルゴリズムについて
スポンサーリンク
概要
- 論文の詳細を見る
三角形を含まない3-正則グラフの最大独立点集合を求める問題(Miscut)とその近似アルゴリズムについて考察を行なう.入力グラフを上記のように制限してもこの問題はNP困難であることが知られている[14].本研究ではこの問題を解く二つの単純な近似アルゴリズムを提案し,それぞれのアルゴリズムの近似比率の評価を行なう.近似アルゴリズムAの近似比率とは,Aが求める独立点点集合の大きさに対する入力グラフGの最大独立点集合の大きさの比と定義する.本研究で考察するアルゴリズムは,グラフの最小次数の頂点を1つ選び独立点集合に加える.そしてこの頂点とこれに隣接するすべての頂点を取り除く.これをグラフがなくなるまで繰り返すものである.これをMINとよぶ.本研究ではMINのMiscutに対する近似比率が上下限ともに漸近的に3/2に一致することを示す.さらにMINの独立点集合の求め方に改良を加えたアルゴリズムMIN^*を提案し,この近似比率の解析をMINと同様に行なった.これよりMIN^*の近似比率は高々10/7であることを示す.そしてこの近似比率の値を29/21よりも小さくできないことを具体的にグラフを構成することにより示す.そしてMIN^*を三角形を含まないr-正則のグラフにも適用できるように拡張を行なう.MINを使って独立点集合を求める時に,最小次数の頂点が複数存在する場合に下手な選び方をしてしまうと最適解を求められないことがある。このような時,MINが迷わずに最適解を求められるようなアドバイスをMINに与えることが可能か否かという問題を考える。本研究ではこの問題に対して反例となるグラフを構成し,否定的な結果を得る.
- 一般社団法人情報処理学会の論文
- 1995-03-17