An Improved Approximate Greedy Algorithm for Vertex Covering
Xiaojun Yang, Lin Guo, Lanxiang Li · 2022
The minimum vertex covering problem is one of the classical NP-Hard problems in combinatorial optimization, which has been widely used in practical problems. The existing approximation algorithms for finding the minimum vertex cover set of a general graph either limit the size of the graph to reduce the complexity, or the algorithm is blind in the search process. This algorithm mainly combines the vertex degree of undirected graph and the idea of greedy algorithm. Considering from the highest degree node of the graph, the vertex with the highest degree is labeled as the optimal selection node, and it is added to the minimum vertex set. Through iteration, the remaining graph is reconstructed, and the node degree associated with the optimal selection node in the previous iteration is recalculated until the minimum vertex coverage set is found. This algorithm has the characteristics of fast convergence and high efficiency, especially for complex and large-scale images, it can quickly obtain the minimum or approximate minimum results.