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

An approximate algorithm for minimum vertex cover set of a graph

已有的求图的最小顶点覆盖集近似算法或者近似比较高,或者为降低时间复杂度限制了图的规模.根据顶点的度分析了图的局部结构特征,提出了悬挂链、封闭链和稠部等重要概念,并在这些概念的基础上提出了相应的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.