An approximate algorithm for minimum vertex cover set of a graph
Xianghui Liu · Ha'erbin gongye daxue xuebao · 2008
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.