clique_number使用的是什么算法？

Question

编号()函数背后的算法是什么？这显然不是一个蛮力的方法，因为它的良好性能。

即使点击“源代码”链接似乎也没有显示出来。这在文档中有解释吗？

Answer 1

clique_number对应于C igraph_clique_number，在最坏情况下复杂度为O(3^(x=V)/3).igraph_clique_number 迭代所有极大团找到了最大的尺寸。

用于寻找所有最大类的算法是与版本有关的.相关的文档 igraph_maximal_cliques说

当前的实现使用了一种改进的Bron算法来寻找最大团，参见: David Eppstein，Maarten L ffler，Bron:在接近最优的时间内在稀疏图中列出所有的最大团。“算法与计算”，“计算机科学”第6506卷，2010年，第403至414页的讲义. 该函数的实现在0.5 ~ 0.6之间，也在0.6 ~ 0.7之间发生了变化，因此，在这三种版本之间，团的顺序和群内的顶点的顺序几乎是不同的。