最大团问题的加权分治算法

• 作者: 宁爱兵 支志兵 杨晓芳 王永斐 陈吉珍
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 分支降阶 最大团问题 加权分治 算法复杂性
• 年，卷（期）: 2016,（2）
• 所属期刊栏目: 理论与研发
• 页码范围: 50-53
• 页数: 4页
• 分类号: TP301.5
• 字数: 4313字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.1403-0138

摘要

分支降阶是目前广泛用于求解组合优化领域中难题的技术之一，该技术的核心思想是将原问题分支成若干个子问题，并递归求解这些子问题。加权分治技术是算法设计和时间复杂度分析中的一种新技术。设计一个基于分支降阶的递归算法求解最大团问题。运用常规技术对该算法进行时间复杂度分析，得出其时间复杂度为O(1.380n p(n))，其中 p(n)表示问题规模数n的多项式函数。运用加权分治技术对原算法进行时间复杂度分析，将该算法的时间复杂度由原来的O(1.380n p(n))降为O(1.325n p(n))。研究结果表明运用加权分治技术能够得到较为精确的时间复杂度。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	宁爱兵	上海理工大学管理学院	59	341	11.0	15.0
2	杨晓芳	上海理工大学管理学院	62	311	10.0	14.0
3	陈吉珍	上海理工大学管理学院	5	11	2.0	3.0
4	支志兵	上海理工大学管理学院	8	14	2.0	3.0
5	王永斐	上海理工大学管理学院	4	9	2.0	3.0