摘要
本文提出了一种求最大完全子图的启发式着色算法.该算法通过为顶点着色将已知无向图划分为极大完全子图的并集,再根据各极大完全子图中顶点的多少选取最大完全子图.随后为提高算法执行效率,又对该算法提出了一种精简措施.最后将该算法运用于一集成电路测试数据编码压缩实验中,证明了该算法对求解最大完全子图的有效性.
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.
出处
《滁州学院学报》
2010年第2期9-11,共3页
Journal of Chuzhou University
基金
安徽省自然科学研究重点项目(KJ2010A352)
安徽省自然科学研究一般项目(KJ2010B224)
宿州学院硕士科研启动基金项目(2009YSS12)
关键词
最大完全子图
极大完全子图
启发式算法
着色算法
maximum complete sub-graph
great complete sub-graph
heuristic algorithm
coloring algorithm
