Improved Greedy Algorithm for the Minimum Vertex Cover Problem
Sheng Zhang · Neimenggu Shi-da xuebao. Zhexue shehui kexue hanwen ban · 2012
Through analyzing the competitive decision algorithm,mixed greedy algorithm and fast reduction algorithm,and based on the concepts of the vertex degree and the idea of the greedy algorithm,the access flag is added to the vertex.Based on these ideas and the concept of decrease and conquer,it is proposed that a relatively neutral greedy algorithm of the minimum vertex cover problem.This algorithm eliminates the concept of adjacency degree,directly using the vertex degree to realize the algorithm,which reduces the time complexity of the algorithm,and easy to programming.In the worst case,the time complexity of the algorithm is O(|V|2).