A hybrid heuristic for the minimum weight vertex cover problem

A hybrid heuristic for the minimum weight vertex cover problem

0.00 Avg rating0 Votes
Article ID: iaor20072107
Country: Singapore
Volume: 23
Issue: 2
Start Page Number: 273
End Page Number: 285
Publication Date: Jun 2006
Journal: Asia-Pacific Journal of Operational Research
Authors: ,
Keywords: heuristics, combinatorial optimization
Abstract:

Given an undirected graph with weights associated with its vertices, the minimum weight vertex cover problem seeks a subset of vertices with minimum sum of weights such that each edge of the graph has at least one endpoint belonging to the subset. In this paper, we propose a hybrid approach, combining a steady-state genetic algorithm and a greedy heuristic, for the minimum weight vertex cover problem. The genetic algorithm generates vertex cover, which is then reduced to minimal weight vertex cover by the heuristic. We have evaluated the performance of our algorithm on several test problems of varying sizes. Computational results show the effectiveness of our approach in solving the minimum weight vertex cover problem.

Reviews

Required fields are marked *. Your email address will not be published.