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: | Singh Alok, Gupta Ashok Kumar |
Keywords: | heuristics, combinatorial optimization |
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.