图论中最大独立集问题的精确算法

计算机工程与应用 ›› 2016, Vol. 52 ›› Issue (1): 20-22.

图论中最大独立集问题的精确算法

陈吉珍，宁爱兵，支志兵，胡琳琳，张惠珍

上海理工大学管理学院，上海 200093

出版日期:2016-01-01 发布日期:2015-12-30

Exact algorithm for maximum independent set problem in graph theory

CHEN Jizhen, NING Aibing, ZHI Zhibing, HU Linlin, ZHANG Huizhen

School of Management, University of Shanghai for Science and Technology, Shanghai 200093, China

Online:2016-01-01 Published:2015-12-30

摘要/Abstract

摘要： 独立集问题是图论和组合数学中常见的NP-hard问题，在许多领域都有着重要的应用。分支降阶是目前广泛用于设计精确算法求解NP-hard问题的技术之一，主要通过快速降阶、分支及递归求解原问题及其子问题。针对图论中最大独立集问题设计了一个分支降阶算法，并通过增加快速降阶规则来降低算法的时间复杂度，最终通过分析得出一个时间复杂度为[O(1.285n)]的精确算法，该算法在理论上得到了一般图的最大独立集的最优解。

null

关键词: 图论, 最小顶点覆盖, 快速降阶, 精确算法

Abstract: Independent set problem is a widely studied NP-hard problem in the area of graph theory and has important applications in many fields. Branch and reduce is widely used tool for obtaining exact solutions for NP-hard and NP-complete problem. The main idea of the approach is to solve the problem by fast reducing the size of it, then decomposing it into sub-problems, recursively solving the sub-problems. In order to speed the running time of the algorithm, it adds some rules to reduce the size of the problem. This paper designs an exact algorithm based on branch and reduce to solve maximum independent set problem, and obtains the worst-case time running of the algorithm that is [O(1.285n)]. The results show that branch and reduce approach can get the exact solution of NP-hard problem in theory.

Key words: graph theory, maximum independent set, branch and reduce, exact algorithm

陈吉珍，宁爱兵，支志兵，胡琳琳，张惠珍. 图论中最大独立集问题的精确算法[J]. 计算机工程与应用, 2016, 52(1): 20-22.

CHEN Jizhen, NING Aibing, ZHI Zhibing, HU Linlin, ZHANG Huizhen. Exact algorithm for maximum independent set problem in graph theory[J]. Computer Engineering and Applications, 2016, 52(1): 20-22.

[1]	孟芸，胡欣，代亮，余雷. 干扰车载网络中增强连通性的资源分配算法[J]. 计算机工程与应用, 2019, 55(7): 9-15.
[2]	刘康1，张雪英1，李凤莲1，田玉楚1，2. 基于通信负载均衡的社交网络图分割方法[J]. 计算机工程与应用, 2018, 54(4): 66-71.
[3]	宫辰，武丽芳，刘维婵，张欣. 不含特殊子式的符号图的选择数[J]. 计算机工程与应用, 2018, 54(16): 55-58.
[4]	刘维婵，张欣. 外1-平面图的均匀点荫度[J]. 计算机工程与应用, 2018, 54(10): 51-53.
[5]	郑艳1，徐国军2，覃锡忠1，贾振红1. 均衡满意度的并行单色连通分支频谱分配算法[J]. 计算机工程与应用, 2014, 50(18): 197-201.
[6]	卢进军1，龙英艳2，潘宏利1. 基于演化图论的可靠的VANETs路由协议[J]. 计算机工程与应用, 2014, 50(13): 96-102.
[7]	张晗1，何东健2. 一种融合纹理信息与图论的图像分割方法[J]. 计算机工程与应用, 2014, 50(1): 180-184.
[8]	韩中1，2，赵升吨2，张贵成2，3，阮卫平3，李建平3，沈红立3. 流程制造系统辨识的自动结构性建模方法[J]. 计算机工程与应用, 2014, 50(1): 227-231.
[9]	曹敦，陈子琦. 一种新的无线传感器网络节点定位算法[J]. 计算机工程与应用, 2012, 48(8): 116-118.
[10]	陈善超，符红光，王颖. 改进的一种图论分割方法在舌像分割中的应用[J]. 计算机工程与应用, 2012, 48(5): 201-203.
[11]	金婷婷，王波，宁爱兵. 最小顶点覆盖问题的竞争决策算法[J]. 计算机工程与应用, 2011, 47(1): 32-34.
[12]	许金星，吴素萍. 旅行售货员问题的图论近似算法[J]. 计算机工程与应用, 2009, 45(32): 51-52.
[13]	应德全¹,应晓敏²,叶继华¹. 一种基于图论的聚类算法NeiMu[J]. 计算机工程与应用, 2009, 45(3): 47-50.
[14]	王凤¹，林杰^1，2. 高校排课问题的图论模型及算法[J]. 计算机工程与应用, 2009, 45(27): 240-242.
[15]	李珂^1，3，连一峰^1，2，3. 一种面向DDoS攻击的网络安全态势评估方法[J]. 计算机工程与应用, 2009, 45(27): 88-91.