The worst-case time complexity for generating all maximal cliques and computational experiments
The worst-case time complexity for generating all maximal cliques and computational experiments
复制标题
DOI：
10.1016/j.tcs.2006.06.015
复制
发表时间：
2006-10-25
影响因子：
1.1
通讯作者：
Takahashi, Haruhisa
中科院分区：
文献类型：
--
作者：
Tomita, Etsuji;Tanaka, Akira;Takahashi, Haruhisa
我们提出了一个深度优先搜索算法生成所有的最大团的无向图，其中修剪方法中的布朗-Kerbosch算法。生成的所有最大团都以树状形式输出。最后证明了对于n-顶点图，其最坏情况时间复杂度为O（3（n/3））。这是最优的，因为在一个n-顶点图中最多存在3（n/3）个最大团。计算实验表明，该算法在实际应用中运行速度非常快。(C)2006 Elsevier B. V.保留所有权利。
We present a depth-first search algorithm for generating all maximal cliques of an undirected graph, in which pruning methods are employed as in the Bron-Kerbosch algorithm. All the maximal cliques generated are output in a tree-like form. Subsequently, we prove that its worst-case time complexity is O(3(n/3)) for an n-vertex graph. This is optimal as a function of it, since there exist up to 3(n/3) maximal cliques in an n-vertex graph. The algorithm is also demonstrated to run very fast in practice by computational experiments. (C) 2006 Elsevier B.V. All rights reserved.