-
题名求一般图的最小顶点覆盖集问题的混合贪婪算法
被引量：6
- 1
-
-
作者
吕健康
张国基
-
机构
华南理工大学理学院
-
出处
《科学技术与工程》
2010年第20期4891-4895,共5页
-
文摘
现有的求一般图的最小顶点覆盖集近似算法或者近似比较高,或者为降低复杂度限制了图的规模,或者算法搜索过程中盲目性大。根据顶点的度特点及贪婪法的思想,提出了邻接度数、覆盖边等主要概念,并在此概念的基础上设计了混合贪婪算法。该算法设计思路清晰,容易理解,易于编程实现,且在最坏情况下的时间复杂度为 O( | V | 2) ,执行效果较好,性能近似比不大于 4/3,接近已知的可能的近似比下界 1. 166 6,低于 2005 年认为最低的近似比 1. 361,是图的最小顶点覆盖问题算法的一个较好的补充。
-
关键词
最小顶点覆盖集
复杂度分析
混合贪婪算法
-
Keywords
minimum vertex cover problem complexity analysis mixed greedy algorithm
-
分类号
O157.5
[理学—基础数学]
-
