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

摘要：

本文提出了一种求最大完全子图的启发式着色算法.该算法通过为顶点着色将已知无向图划分为极大完全子图的并集,再根据各极大完全子图中顶点的多少选取最大完全子图.随后为提高算法执行效率,又对该算法提出了一种精简措施.最后将该算法运用于一集成电路测试数据编码压缩实验中,证明了该算法对求解最大完全子图的有效性.

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

所属期刊栏目：12

分类号：O157.6(代数、数论、组合理论)

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

在线出版日期：2010-08-31（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：9-11