問題タブ [clique-problem]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
complexity-theory - 言語の補語はNPのCLIQUE要素ですか？
私はNPクラスとスライドの1つについて勉強しています：
CLIQUE の補数が NP の要素であるかどうか、証明されたことはありますか?
また、その証拠はありますか？
algorithm - クリークパーコレーションアルゴリズム
私は長い間検索してきましたが、クリークパーコレーションを見つけるための最良の方法は何かを理解できませんでした. 私が見る限り、2つの方法があります
- グラフ G でサイズ k のクリークを見つけ、隣接するクリーク ノード間にグラフを作成します。
- サイズ >= k-1 の最大クリークを見つけて、隣接するクリーク ノード間のグラフを作成します。
max-cliques を見つけることは NP-Complete 問題であることを知っているので、グラフ G で k cliques を見つけることは多項式であることを理解しているので、最初の方法はより効率的ですか? 誰かが問題を解決して解決できれば幸いです。ありがとうございます。
networkx - Networkx find_cliques() 関数を理解する
私は現在、グラフ内のクリークを見つけるためのアルゴリズムを作成しようとしていますが、幸運にもそれを行う関数について Networkx のドキュメントを見つけました。残念ながら、変数名は少し簡潔で、コードの各部分が何をするのか理解できません。
find_cliques のコードは次のとおりです。
それはうまく機能しますが、ここで何が起こっているのかを理解したいだけで、それを説明するオンラインのリソースが見つからないようです.