An efficient simulated annealing algorithm for the minimum vertex cover problem

The minimum vertex cover problem is a classic graph optimization problem. It is well known that it is an NP-complete problem. In this paper, an efficient simulated annealing algorithm is presented for the minimum vertex cover problem. In this algorithm, an acceptance function is defined for every vertex. This can help the algorithm in finding a near-optimal solution to a problem. Simulations are performed on several benchmark graphs, and the simulation results show that the proposed algorithm provides a high probability of finding optimal solutions.