中規模グラフのクリーク列挙

Question

中規模のグラフ（570ノード、69127辺、密度：g42形式の0.42）を持ち、Nより大きい（例えば5）すべてのクリークを列挙したいと思います。最も効率的な方法は何ですか？私は一般的な言語やソフトウェアパッケージでライブラリを探しています。

Answer 1

SNAP network analysis libraryを使用できます。これは、Tomita et al。 2006アルゴリズム。他のすべての理論的に高速のアルゴリズムは、Tomitaらよりも著しく遅いことが示されている。実際には、少なくとも疎なグラフの場合（Eppstein et al。2010）。

もしそのアルゴリズムが大きなグラフのためにあまりにも多くのメモリを必要とするならば、Eppsteinらの線形空間アルゴリズムを試すことができます。 2010/2011

• 富田（富田）E。全ての最大クリークを生成するための最悪の場合の計算量および計算実験。理論コンピュータ科学、2006,363,28-42。DOI:10.1016/j.tcs.2006.06.015

• Eppstein、D .; Löffler、M. & Strash、D. Cheong、O.最適に近い時間にスパースグラフのすべての最大クリークをリストアップする。 ISAAC '10：Proc。第21回アルゴリズムと計算に関する国際シンポジウム、Springer Berlin/Heidelberg、2010、6506、403-414 DOI:10.1007/978-3-642-17517-6_36

• Eppstein、D. & Strash、D.大きなスパースの実世界グラフのすべての最大クリークをリストアップします。 SEA'11：Proc。第10回実験アルゴリズムに関する国際シンポジウム、Springer Berlin/Heidelberg、2011、6630、364-375 DOI:10.1007/978-3-642-20662-7_31