最大クリーク問題とは? わかりやすく解説

Weblio 辞書 > 学問 > OR事典 > 最大クリーク問題の意味・解説 

最大クリーク問題

「OR事典」の他の用語
組合せ最適化:  巡回セールスマン問題  整数計画  施設配置問題  最大クリーク問題  最小木問題  最短路問題  最適性の原理

最大クリーク問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/02/13 05:21 UTC 版)

ナビゲーションに移動 検索に移動
このグラフは最大クリーク {1, 2, 5} を持つ

最大クリーク問題(さいだいクリークもんだい)は、グラフ理論において、グラフ中のクリーク(任意の二頂点間に枝があるような頂点集合)の中で最大のものを見つける問題[1]NP困難であることが知られている。

この問題は、補グラフに対する最大独立集合問題と等価である。

近似アルゴリズムについても研究されているが、グラフの頂点数を n とするとき、近似度 O(n / (log n)2) が達成されているのみである。また、P = NP が成り立たないとき、任意の ε > 0 について、近似度 n1/2 − ε の近似アルゴリズムが存在しないことが示されている。NP = ZPP が成り立たない場合、近似度 n1 − ε の近似アルゴリズムが存在しないことも示されている。

脚注

参考文献

関連項目

外部リンク



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「最大クリーク問題」の関連用語

最大クリーク問題のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



最大クリーク問題のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2025 (社)日本オペレーションズ・リサーチ学会 All rights reserved.
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの最大クリーク問題 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS