求最大完全子图的启发式着色算法  

Heuristic Coloring Algorithm for a Maximum Complete Sub-graph

作　　者：李建新[1,2] 

机构地区：[1]宿州学院计算机科学与技术系人工智能与数据挖掘研究室,安徽宿州234000 [2]合肥工业大学计算机与信息学院,安徽合肥230009

出　　处：《滁州学院学报》2010年第2期9-11,共3页Journal of Chuzhou University

基　　金：安徽省自然科学研究重点项目(KJ2010A352);安徽省自然科学研究一般项目(KJ2010B224);宿州学院硕士科研启动基金项目(2009YSS12)

摘　　要：本文提出了一种求最大完全子图的启发式着色算法.该算法通过为顶点着色将已知无向图划分为极大完全子图的并集,再根据各极大完全子图中顶点的多少选取最大完全子图.随后为提高算法执行效率,又对该算法提出了一种精简措施.最后将该算法运用于一集成电路测试数据编码压缩实验中,证明了该算法对求解最大完全子图的有效性.A heuristic coloring algorithm for a maximum complete sub-graph was put forward.According to the algorithm,a known undirected graph was made into a union of great complete sub-graphs by coloring the vertices,and then a maximum complete sub-graph was selected according to the number of vertices in each great complete sub-graph.Subsequently,in order to improve the execution efficiency of the algorithm,it was simplified.It was finally put into use in an experiment of test data coding compression of an integrated circuit,which proved that it was effective in determining a maximum complete sub-graph.

关 键 词：最大完全子图 极大完全子图 启发式算法 着色算法 

分 类 号：O157.6[理学—数学]