A HYBRID HEURISTIC FOR THE MINIMUM WEIGHT VERTEX COVER PROBLEM

Alok Singh () and Ashok Kumar Gupta ()
Additional contact information
Alok Singh: J. K. Institute of Applied Physics and Technology, Faculty of Science, University of Allahabad, Allahabad – 211002, India
Ashok Kumar Gupta: J. K. Institute of Applied Physics and Technology, Faculty of Science, University of Allahabad, Allahabad – 211002, India

Asia-Pacific Journal of Operational Research (APJOR), 2006, vol. 23, issue 02, 273-285

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: Combinatorial optimization; greedy heuristic; minimum weight vertex cover; steady-state genetic algorithm (search for similar items in EconPapers)
Date: 2006
References: View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595906000905
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:23:y:2006:i:02:n:s0217595906000905

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595906000905

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().