派系号码使用什么算法？

Question

python-igraph's clique_number()函数背后的算法是什么？考虑到它的良好性能，这显然不是一种暴力方法。你知道吗

即使点击“源代码”链接，似乎也没有透露出来。文件里有没有解释？你知道吗

Answer 1

clique_number对应于C^{}，最坏情况复杂度为O（3^（| V |/3））。igraph_clique_numberiterates over all maximal cliques并找到最大的大小。你知道吗

用于寻找所有最大团的算法是版本相关的。相关igraph_maximal_cliques的docs表示

The current implementation uses a modified Bron-Kerbosch algorithm to find the maximal cliques, see: David Eppstein, Maarten Löffler, Darren Strash: Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time. Algorithms and Computation, Lecture Notes in Computer Science Volume 6506, 2010, pp 403-414.

The implementation of this function changed between igraph 0.5 and 0.6 and also between 0.6 and 0.7, so the order of the cliques and the order of vertices within the cliques will almost surely be different between these three versions.