摘要
提出了关于最大团问题的一种新思路基于平均度排序的局部枚举算法.对于一般的随机图G而言,图中含有最大团(d(G)+1)-团的概率要明显大于δ(G)-团或Δ-团.此算法通过了在随机图上进行实算的测试.实际计算结果表明:基于平均度排序的枚举算法比目前一般的基于枚举思想的算法更有效,其程序易于并行执行,值得进一步研究.
A new algorithm for the maximum clique problem has been presented in this paper, the local enumerative algorithm based on average degree sorting. For a random graph G, the probability of containing （d（G）＋1）-clique in G is obviously bigger than that of containing δ（G）-clique or △ （G）-clique. Practical operating of this algorithm on random graph indicates that, compared with other algorithms, the algorithm proposed in this paper is more effective easier to operate.
出处
《中北大学学报（自然科学版）》
CAS
2006年第2期180-182,共3页
Journal of North University of China(Natural Science Edition)
基金
山西省自然科学基金资助项目(20041005)
关键词
最大团
平均度
枚举算法
随机图
maximum clique
average degree
enumerative algorithm
random graph
