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.
Join Sparrho today to stay on top of science
Discover, organise and share research that matters to you