algorithm - 連結グラフの K クリーク

Question

クリーク問題 (特に k-clique) に関する質問です。そのようなクリークが存在する場合、接続されたグラフのプロパティを利用して特定のサイズのクリークを見つけるアルゴリズムはありますkか?

Answer 1

任意のアルゴリズムを作成して、連結要素を利用できます。アルゴリズムを実行する前に、接続されたコンポーネントを見つけて、より小さいものを破棄kし、残りのコンポーネントごとにアルゴリズムを個別に実行します。