一个新的极大独立集算法及独立数的界

• 作者: 丁根宏 李勤丰 李尤丰
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 极大独立集 界 贪婪算法 图论
• 年，卷（期）: 2008,（26）
• 所属期刊栏目: 理论研究
• 页码范围: 48-50
• 页数: 3页
• 分类号: O157.6|TP39
• 字数: 2310字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2008.26.014

摘要

最大独立集问题是图论中典型的组合优化问题,有着广泛的实际应用价值.分析了现有独立数的界公式后给出了新的上界公式,并通过分析贪婪算法和独立集自身的特征,给出了新的求解极大独立集的算法,并证明了其确定性.然后用实例验证了该算法的有效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	丁根宏	河海大学理学院	31	127	6.0	10.0
2	李尤丰	金陵科技学院信息技术学院	19	63	4.0	7.0
3	李勤丰	金陵科技学院基础部	10	17	3.0	3.0