基于图着色的极大团求解算法  

作　　者：李向祥 贾西贝[1] 

机构地区：[1]兰州交通大学电子与信息工程学院,甘肃兰州730070

出　　处：《甘肃科技》2014年第19期14-18,共5页Gansu Science and Technology

摘　　要：极大团问题是图论中一个经典的组合优化问题,也是一类NP完全问题,在国际上已有广泛的研究。作者在对其他现有极大团求解算法进行研究之后,设计了一种基于图着色思想的极大团求解算法。基本思想是通过不同的方式对随机图的相应补图进行顶点着色,寻找出所有顶点的极大独立集。而后返回到原图之中找出极大团,并且通过比较删减寻找到随机图的所有极大团。

关 键 词：极大团问题 图着色 极大独立集 

分 类 号：TP399[自动化与计算机技术—计算机应用技术]