求图的最小顶点覆盖集的一个近似算法

作     者：闫兴篡 殷建平 蔡志平 刘湘辉 YAN Xing-cuan;YIN Jian-ping;CAI Zhi-ping;LIU Xiang-hui

作者机构：国防科技大学计算机学院长沙410073 

基　　金：国家自然科学基金资助项目(60373023) 湖南省自然科学基金资助项目(06JJ30035) 

出 版 物：《哈尔滨工业大学学报》 (Journal of Harbin Institute of Technology)

年 卷 期：2008年第40卷第7期

页      码：1131-1135页

摘      要：已有的求图的最小顶点覆盖集近似算法或者近似比较高,或者为降低时间复杂度限制了图的规模.根据顶点的度分析了图的局部结构特征,提出了悬挂链、封闭链和稠部等重要概念,并在这些概念的基础上提出了相应的3个伪最小覆盖点选取启发式策略.运用这些伪最小覆盖点选取启发式策略设计了一个近似算法.该算法不限制图的规模,时间复杂度为O(|V|2),近似比为4/3,接近已知的可能的近似比下界1.1666,低于2005年认为最低的近似比1.361.与同类算法相比,该算法设计思路清晰,容易理解,易于编程实现,执行效果好,是图的最小顶点覆盖集问题的近似算法的一个重要补充.

主 题 词：最小顶点覆盖集 近似算法 近似比 运行时间 NP难问题 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

核心收录：

D　O　I：10.3321/j.issn:0367-6234.2008.07.029

馆 藏 号：203540844...