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

An approximate algorithm for minimum vertex cover set of a graph

作　　者：闫兴篡[1] 殷建平[1] 蔡志平[1] 刘湘辉[1] 

机构地区：[1]国防科技大学计算机学院,长沙410073

出　　处：《哈尔滨工业大学学报》2008年第7期1131-1135,共5页Journal of Harbin Institute of Technology

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

摘　　要：已有的求图的最小顶点覆盖集近似算法或者近似比较高,或者为降低时间复杂度限制了图的规模.根据顶点的度分析了图的局部结构特征,提出了悬挂链、封闭链和稠部等重要概念,并在这些概念的基础上提出了相应的3个伪最小覆盖点选取启发式策略.运用这些伪最小覆盖点选取启发式策略设计了一个近似算法.该算法不限制图的规模,时间复杂度为O(|V|2),近似比为4/3,接近已知的可能的近似比下界1.1666,低于2005年认为最低的近似比1.361.与同类算法相比,该算法设计思路清晰,容易理解,易于编程实现,执行效果好,是图的最小顶点覆盖集问题的近似算法的一个重要补充.Approximate algorithms now available for solving the minimum vertex cover set of a graph either have a high ratio bound or constrain the scale of the graph intending to reduce the running time. Based on the analysis of the vertex degree, this paper proposes three important notions： pendulous link, close link and density part. According to these notions, three heuristic policies for selecting pseudo minimum-cover-vertex are proposed. With these policies, this paper presents an approximate algorithm for the minimum vertex cover set of a graph. The algorithm, without any constraint on the scale of the graph, has a total running time of O（｜V｜^2） and a ratio bound of 4/3, close to the known potential ratio bound of 1.166 6, and better than that of 1.361 in 2005. Compared with the existing algorithms, the proposed algorithm shows a higher efficiency. Furthermore, it has a clear clue and is easy to be programmed. The algorithm can be a valuable supplement for the approximate algorithm to find the minimum vertex cover set of a graph.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]