最大团问题研究_最大团问题的时间复杂度

分支限界算法

很久之前 1963年之前？

时间复杂度为O(n2^(n))

大体思路

比如对于一个图g，它已经包含了{1,2}并且，我们知道它是按照1,2的顺序放入的，即最后放入的那个点是2，搜索原图所有的顶点，找到一个点x使得：2与x相连，x与g原先有的顶点相连（x与1相连）。那么对于图g的下一个图h就有{1,2,x}放入队列。继续寻找下一个顶点y。依次类推，直到队列为空。
1

Bron–Kerbosch算法

1973发布 时间复杂度为O(3^(n/3))

算法流程

BronKerbosch1(R, P, X): 
 if P and X are both empty: 
 report R as a maximal clique 
for each vertex v in P: 
 BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v)) 
 P := P \ {v} 
 X := X ⋃ {v}
1
2
3
4
5
6
7

大体思路：

其中R为已选点的集合，P为可选点的集合，X为没有选择的点的集合。

每次从P中选择一个点，加入已选点集合，搜索完后加入没有选择的点的集合，并把自己从可选择点中删除。

检查只需要检查没有选择的点和当前所有已经选择的点的所有邻接点是否有并集即可（如果有则不是极大团）。

图着色子分支，以MaxCliqueDyn为例

2007年 时间复杂度 O(3^(n/3))？

大致思路 先对图着色 然后根据着色的信息找最大团

Procedure MaxCliqueDyn(R, C, level)
       S[level] := S[level] + S[level−1] − Sold[level];
       Sold[level] := S[level−1];
       while R ≠ Ø do
           choose a vertex p with maximum C(p) (last vertex) from R;
           R := R\{p};
           if |Q| + C[index of p in R] > |Qmax| then
               Q := Q ⋃ {p};
               if R ⋂ Γ(p) ≠ Ø then
                   if S[level]/ALL STEPS < Tlimit then
                       calculate the degrees of vertices in G(R ⋂ Γ(p));
                       sort vertices in R ⋂ Γ(p) in a descending order
                       with respect to their degrees;
                   end if
                   ColorSort(R ⋂ Γ(p), C')
                   S[level] := S[level] + 1;
                   ALL STEPS := ALL STEPS + 1;
                   MaxCliqueDyn(R ⋂ Γ(p), C', level + 1);
               else if |Q| > |Qmax| then Qmax := Q;
               Q := Q\{p};
           else return
       end while
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

代码大致流程 和BronKerbosch有相似之处，时间复杂度也是指数级别的

近似算法分支

大致思路 在一个区域求解极大团，然后以某种方式跳到另外一个区域，再次求解极大团。跳的方式，目前流行的有模拟退火，遗传算法，都不能保证全局最优解。具体不展开了。