Paper Info
Title
A Hybrid Heuristic for the Minimum Weight Vertex Cover Problem
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.
Year
DOI
Venue
2006
10.1142/S0217595906000905
ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH
Keywords
Field
DocType
combinatorial optimization,greedy heuristic,minimum weight vertex cover,steady-state genetic algorithm
Discrete mathematics,Mathematical optimization,Combinatorics,Prim's algorithm,Edge cover,Vertex (graph theory),Neighbourhood (graph theory),Degree (graph theory),Vertex cover,Kruskal's algorithm,Feedback vertex set,Mathematics
Journal
Volume
Issue
ISSN
23
2
0217-5959
Citations 
PageRank 
References 
11
0.96
7
Authors
2
Name
Order
Citations
PageRank
Alok Singh120117.15
Ashok Kumar Gupta2352.67