A HYBRID HEURISTIC FOR THE MINIMUM WEIGHT VERTEX COVER PROBLEM
- 1 June 2006
- journal article
- Published by World Scientific Pub Co Pte Ltd in Asia-Pacific Journal of Operational Research
- Vol. 23 (2), 273-285
- https://doi.org/10.1142/s0217595906000905
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.Keywords
This publication has 10 references indexed in Scilit:
- An Ant Colony Optimization Algorithm for the Minimum Weight Vertex Cover ProblemAnnals of Operations Research, 2004
- Ant Colony OptimizationPublished by MIT Press ,2004
- Ant Colony Optimization and Swarm IntelligenceLecture Notes in Computer Science, 2004
- Some optimal inapproximability resultsJournal of the ACM, 2001
- An improved fixed-parameter algorithm for vertex coverInformation Processing Letters, 1998
- A survey of approximately optimal solutions to some covering and packing problemsACM Computing Surveys, 1997
- Fixed-Parameter Tractability and Completeness I: Basic ResultsSIAM Journal on Computing, 1995
- Ramsey numbers and an approximation algorithm for the vertex cover problemActa Informatica, 1985
- A modification of the greedy algorithm for vertex coverInformation Processing Letters, 1983
- A Greedy Heuristic for the Set-Covering ProblemMathematics of Operations Research, 1979