摘要：Minimum vertex cover problem(Min-VC) on a graph is a NP-hard problem. The neighborhoods of a vertex are analyzed in this paper, and so are the information they hold for judging whether the vertex is belong to Min-VC or not. Then, the concept of Max-I share degree is put forword in order to qualify the possibility of a vertex to be collected into Min-VC. Based on Max-I share degree, a heuristic algorithm is proposed. Our algorithm has two remarkable characteristics: one is that it is able to get almost the same Min-VC as that of an exact algorithm, and the approximation degree is obviously better than that of other approximation algorithms; the other is that it has polynomial time complexity. Emulational results show that the running time is significantly less than those of other algorithms.
