2

私は中規模のグラフ (570 ノード、69127 エッジ、密度: gexf 形式で 0.42) を持っており、N (たとえば 5) より大きいサイズのすべてのクリークを列挙したいと考えています。利用可能な最も効率的な方法は何ですか? 一般的な言語またはソフトウェア パッケージのライブラリを探しています。

4

1 に答える 1

1

Tomita et al. を実装したSNAP ネットワーク解析ライブラリを使用できます。2006 アルゴリズム。他のすべての理論的に高速なアルゴリズムは、富田らよりも大幅に遅いことが示されています。実際には、少なくともまばらなグラフの場合 (Eppstein et al. 2010)。

そのアルゴリズムが大きなグラフに必要なメモリが多すぎる場合は、Eppstein らの線形空間アルゴリズムを試すことができます。2010/2011。

  • 富田 恵。Tanaka, A. & Takahashi, H. すべての最大クリークと計算実験を生成するための最悪の場合の時間計算量。理論的コンピューター サイエンス、2006 年、363、28 ～ 42。DOI:10.1016/j.tcs.2006.06.015

  • エプスタイン、D.; Löffler, M. & Strash, D. Cheong, O. スパース グラフ内のすべての最大クリークをほぼ最適な時間でリストします。ISAAC '10: Proc. アルゴリズムと計算に関する第 21 回国際シンポジウム、シュプリンガー ベルリン/ハイデルベルク、2010 年、6506、403-414。DOI:10.1007/978-3-642-17517-6_36

  • Eppstein, D. & Strash, D. 大規模なまばらな現実世界のグラフにすべての最大クリークをリストします。SEA '11: Proc. 実験的アルゴリズムに関する第 10 回国際シンポジウム、シュプリンガー ベルリン/ハイデルベルク、2011 年、6630、364-375。DOI:10.1007/978-3-642-20662-7_31

于 2012-10-03T01:24:01.277 に答える