密な部分グラフ問題の貪欲解法

概要

論文の詳細を見る
枝が非負の値で重み付けされたn頂点のグラフと正整数k ≤ nが与えれた時, 我々はk頂点の部分グラフで最も重みの大きいものを見つけたい. ここでは次のような貪欲アルゴリズムの性能を調べる:最小次数の頂点をグラフから取り除くことをちょうどk頂点が残るまで繰り返す. このアルゴリズムの最悪近似比Rに対して, 次のようにほぼ一致する上下界を与える:n/3 ≤ k ≤ nの範囲のkに対して(1/2+n/(2k))^2-O(1/n) ≤ R ≤ (1/2+n/(2k))^2+O(1/n), k < n/3の範囲のkに対して2(n/k-1)- O(1/k) ≤ R ≤ 2(n/k-1)+O(n/k^2). 例えばk=n/2の時この上下界は9/4±O(1/n)であり, 素朴な上界4と下界2を改良している. 一般のkに対する上界はこの単純なアルゴリズムが, k ≥ n^<11/18>の範囲ではこれまでに知られていた最良のアルゴリズムよりも少なくとも2倍優れていることを示している.
社団法人電子情報通信学会の論文
1996-01-26