改进的最小顶点覆盖问题的贪婪算法

• 作者: 张升 张楠
• 来源期刊: 内蒙古师范大学学报（自然科学汉文版）
• 学科: 工学
• 关键词: 最小顶点覆盖问题 贪婪算法 顶点的度 访问标记 减治法
• 年，卷（期）: 2012,（2）
• 所属期刊栏目: 计算机科学与技术
• 页码范围: 206-210
• 分类号: TP319
• 字数: 3358字
• 语种: 中文
• DOI: 10.3969/j.issn.1001-8735.2012.02.020

摘要

通过分析竞争决策算法、混合贪婪算法和快速降阶算法,在顶点的度及贪心算法的基础上,对顶点添加访问标记符号,并在减治法的概念下设计了最小顶点覆盖问题的一种较为中和性的贪婪算法.该算法消除了邻接度数的概念,直接运用顶点度数来完成算法的实现,从而降低了算法的时间复杂度,且更易于编程.该算法在最坏情况下的时间复杂度为O(|V|2).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张升	内蒙古师范大学公共管理学院	21	46	4.0	5.0
2	张楠	内蒙古师范大学计算机与信息工程学院	9	9	2.0	2.0