「最大クリーク問題」の版間の差分
提供: miniwiki
ja>ARAKI Satoru (+img, ref) |
細 (1版 をインポートしました) |
(相違点なし)
|
2018/8/19/ (日) 17:38時点における最新版
最大クリーク問題(さいだいクリークもんだい)は、グラフ理論において、グラフ中のクリーク(任意の二頂点間に枝があるような頂点集合)の中で最大のものを見つける問題[1]。NP困難であることが知られている。
近似アルゴリズムについても研究されているが、グラフの頂点数を n とするとき、近似度 O(n / (log n)2) が達成されているのみである。また、P = NP が成り立たないとき、任意の ε > 0 について、近似度 n1/2 − ε の近似アルゴリズムが存在しないことが示されている。NP = ZPP が成り立たない場合、近似度 n1 − ε の近似アルゴリズムが存在しないことも示されている。
脚注
参考文献
- (1998) Combinatorial optimization: algorithms and complexity. Dover Publications. ISBN 978-0-486-40258-1.