顶点编码方法对最大团算法影响的研究

计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (3): 173-174.

顶点编码方法对最大团算法影响的研究

吴卫江,李国和

中国石油大学计算机科学与技术系，北京 102200

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2008-01-21 发布日期:2008-01-21
通讯作者: 吴卫江

Research on effect of vertex encoding method to maximum clique algorithm

WU Wei-jiang,LI Guo-he

Department of Computer Science and Technology，China University of Petroleum，Beijing 102200，China

Received:1900-01-01 Revised:1900-01-01 Online:2008-01-21 Published:2008-01-21
Contact: WU Wei-jiang

摘要/Abstract

摘要： 最大团算法是基于图数据挖掘的一个重要算法，提高最大团算法效率是研究的重点。以一个典型的精确求解最大团算法为基础，分析了两种顶点编码方法对最大团算法的影响，并在随机图上做了对比实验，验证了在不改变算法的前提下，通过改变顶点编码方法也可以提高最大团算法效率的结论。

关键词: 最大团算法, 顶点编码方法, 算法效率

Abstract: Maximum clique algorithm is an important algorithm of graph-based data mining.Improve the efficiency of maximum clique algorithm is the emphasis of research.Based on a typical maximum clique algorithm，the effect of two kinds of vertex encoding method to maximum clique algorithm is analyzed in this paper.A contrast experiment on random graph validates that without changing the algorithm，the efficiency of maximum clique algorithm can be improved by changing vertex encoding method.

Key words: maximum clique algorithm, vertex encoding method, efficiency of algorithm

吴卫江,李国和. 顶点编码方法对最大团算法影响的研究[J]. 计算机工程与应用, 2008, 44(3): 173-174.

WU Wei-jiang,LI Guo-he. Research on effect of vertex encoding method to maximum clique algorithm[J]. Computer Engineering and Applications, 2008, 44(3): 173-174.