加权分治与皇冠技术求解最大加权独立集

• 作者: 何咏梅 刘志民 宁爱兵 张惠珍 黄飞
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 皇冠分解 加就权独立集 加权分治算法 分支降阶
• 年，卷（期）: 2017,（9）
• 所属期刊栏目: 热点与综述
• 页码范围: 26-30,110
• 页数: 6页
• 分类号: TP301.6
• 字数: 4849字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.1612-0474

摘要

皇冠分解技术是一种算法优化技术,通过找出一个称为皇冠的特殊非空独立集,并将该独立集和它的邻接集合删除,得到一个不含皇冠的子图,从而降低原问题规模,降低算法时间复杂度.针对加权图的独立集问题相关性质设计了精确算法来找出一个权值之和最大的加权独立集.首先构造了一个二分图,并通过该图找出皇冠结构,采用皇冠分解技术分解图,针对无皇冠的子图设计了一个分支降阶递归算法,然后利用加权分治技术对算法时间复杂度进行分析,最终得到一个优于常规时间复杂度的精确算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	宁爱兵	上海理工大学管理学院	59	341	11.0	15.0
2	张惠珍	上海理工大学管理学院	86	662	16.0	23.0
3	黄飞	上海理工大学管理学院	6	5	2.0	2.0
4	刘志民	上海理工大学管理学院	4	3	1.0	1.0
5	何咏梅	上海理工大学管理学院	1	0	0.0	0.0