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

• 作者: 宁爱兵 张惠珍 支志兵 胡琳琳 陈吉珍
• 来源期刊: 计算机工程与应用
• 学科: 数学
• 关键词: 图论 最小顶点覆盖 快速降阶 精确算法
• 年，卷（期）: 2016,（1）
• 所属期刊栏目: 理论与研发
• 页码范围: 20-22,109
• 页数: 4页
• 分类号: O223
• 字数: 3411字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.1503-0144

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	宁爱兵	上海理工大学管理学院	59	341	11.0	15.0
2	张惠珍	上海理工大学管理学院	86	662	16.0	23.0
3	陈吉珍	上海理工大学管理学院	5	11	2.0	3.0
4	支志兵	上海理工大学管理学院	8	14	2.0	3.0
5	胡琳琳	上海理工大学管理学院	4	5	2.0	2.0