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

• 作者: 孙艳蕊
• 来源期刊: 小型微型计算机系统
• 学科: 工学
• 关键词: 极大独立集 邻接矩阵 二分树
• 年，卷（期）: 2013,（8）
• 所属期刊栏目: 人工智能与算法研究
• 页码范围: 1862-1865
• 页数: 4页
• 分类号: TP301
• 字数: 4255字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	孙艳蕊	东北大学理学院	40	182	8.0	11.0