next up previous
: 最大充足割当問題(MAX-SAT) : 近似アルゴリズムでよく取り扱われる問題(代表的なものの一部) : 巡回セールスマン問題(TSP)

最大クリーク問題(MAX-CLIQUE)

入力グラフGに対し, どの2点間にも辺が存在するようなGの部分グラフで 最大のものを求める. 例えば, 以下の図では, 左から2番目の部分グラフは対角線が抜けているので クリークではない. 右の2つのグラフはクリークであるが, 右から2番目はサイズが3だが一番右は サイズが5で大きい.



Koichi Yamazaki 平成12年3月15日