A hybridized tabu search approach for the minimum weight vertex cover problem

Research paper by Stefan Voß, Andreas Fink

Indexed on: 19 Sep '12Published on: 19 Sep '12Published in: Journal of Heuristics


The minimum weight vertex cover problem is a basic combinatorial optimization problem defined as follows. Given an undirected graph and positive weights for all vertices the objective is to determine a subset of the vertices which covers all edges such that the sum of the related cost values is minimized. In this paper we apply a modified reactive tabu search approach for solving the problem. While the initial concept of reactive tabu search involves a random walk we propose to replace this random walk by a controlled simulated annealing. Numerical results are presented outperforming previous metaheuristic approaches in most cases.