A New Mixed Greedy Algorithm for Solving Minimum Vertex Cover Set Problems
Guoji Zhang · Science Technology and Engineering · 2010
Existing approximate algorithms for searching the minimum vertex cover set of a given graph either have a higher ratio bound or constrain the scale of the graph intending to reduce the computational complexity or shows big blindness for the algorithm searching.Based on the characteristics of the vertex degree and the idea of the greedy algorithm,the two primary concepts of abutting degree and vertex cover border are proposed.According to these concepts,a new mixed greedy algorithm is proposed.This proposed algorithm shows a higher efficienct,more understandable and easier for computer implementation.Theoretically,it has a computational time of O(| V | 2) and a ratio bound of 4 /3.This ratio bound is close to the known potential ratio bound of 1.166 6,and better than the result of 1.361 in 2005.The algorithm is a valuable alternative to find the minimum vertex cover set of a given graph.