最优顶点覆盖的贪心边近似算法

• 作者: 杨杰 王玲
• 来源期刊: 四川师范大学学报（自然科学版）
• 学科: 工学
• 关键词: 贪心边 单点贪心边 双点贪心边 顶点覆盖 近似算法
• 年，卷（期）: 2006,（2）
• 所属期刊栏目: 技术研究
• 页码范围: 244-248
• 页数: 5页
• 分类号: TP301.6
• 字数: 3663字
• 语种: 中文
• DOI: 10.3969/j.issn.1001-8395.2006.02.029

摘要

提出了一种新的贪心边近似算法,能保证性能比不大于2的同时比传统的选任意边算法有更优的解,在可验证(能得到最优覆盖点数)时,统计数据表明贪心边算法非常有效,是一个集合了传统的任选一边近似算法和选择度数最大点的贪心算法两者优点的新算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王玲	四川师范大学计算机科学学院	40	402	10.0	18.0