私は長い間検索してきましたが、クリークパーコレーションを見つけるための最良の方法は何かを理解できませんでした. 私が見る限り、2つの方法があります
- グラフ G でサイズ k のクリークを見つけ、隣接するクリーク ノード間にグラフを作成します。
- サイズ >= k-1 の最大クリークを見つけて、隣接するクリーク ノード間のグラフを作成します。
max-cliques を見つけることは NP-Complete 問題であることを知っているので、グラフ G で k cliques を見つけることは多項式であることを理解しているので、最初の方法はより効率的ですか? 誰かが問題を解決して解決できれば幸いです。ありがとうございます。