一个求无向图所有极大独立集的算法

摘要：

图的极大独立集在计算机视觉、计算机网络、编码理论和资源配置等领域有着广泛的应用.本文利用图的分解方法给出了一个求简单无向图所有极大独立集的递归公式.定义了图的邻接矩阵的两个变换和点集合的一些运算.在此基础上,利用二分树给出了一个求无向图的所有极大独立集的有效算法.算法的时间复杂度是O(mn),其中m,n分别是图的所有极大独立集数和顶点个数.算法只需对网络的邻接矩阵进行处理,在计算机上实现起来非常方便.最后,通过实例验证了算法的有效性.

关键词：极大独立集、邻接矩阵、二分树

所属期刊栏目：34

分类号：TP301(计算技术、计算机技术)

资助基金：辽宁省自然科学基金项目201202074

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

页数：共4页

页码：1862-1865