求一般图的最小顶点覆盖集问题的混合贪婪算法

摘要：

现有的求一般图的最小顶点覆盖集近似算法或者近似比较高,或者为降低复杂度限制了图的规模,或者算法搜索过程中盲目性大.根据顶点的度特点及贪婪法的思想,提出了邻接度数、覆盖边等主要概念,并在此概念的基础上设计了混合贪婪算法.该算法设计思路清晰,容易理解,易于编程实现,且在最坏情况下的时间复杂度为O(|V|2),执行效果较好,性能近似比不大于4/3,接近已知的可能的近似比下界1.166 6,低于2005年认为最低的近似比1.361,是图的最小顶点覆盖问题算法的一个较好的补充.

关键词：最小顶点覆盖集、复杂度分析、混合贪婪算法

所属期刊栏目：10

分类号：O157.5(代数、数论、组合理论)

在线出版日期：2010-09-13（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：4891-4895