IDEAS home Printed from https://ideas.repec.org/a/wsi/apjorx/v23y2006i02ns0217595906000905.html
   My bibliography  Save this article

A Hybrid Heuristic For The Minimum Weight Vertex Cover Problem

Author

Listed:
  • 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)

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.

Suggested Citation

  • Alok Singh & Ashok Kumar Gupta, 2006. "A Hybrid Heuristic For The Minimum Weight Vertex Cover Problem," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 23(02), pages 273-285.
    • Handle: RePEc:wsi:apjorx:v:23:y:2006:i:02:n:s0217595906000905
    DOI: 10.1142/S0217595906000905
    as

    Download full text from publisher

    File URL: http://www.worldscientific.com/doi/abs/10.1142/S0217595906000905
    Download Restriction: Access to full text is restricted to subscribers
    File URL: https://libkey.io/10.1142/S0217595906000905?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Raka Jovanovic & Antonio P. Sanfilippo & Stefan Voß, 2022. "Fixed set search applied to the multi-objective minimum weighted vertex cover problem," Journal of Heuristics, Springer, vol. 28(4), pages 481-508, August.
    2. Imran Khan & Naveed Riaz, 2015. "A new and fast approximation algorithm for vertex cover using a maximum independent set (VCUMI)," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 25(4), pages 5-18.
    3. Taoqing Zhou & Zhipeng Lü & Yang Wang & Junwen Ding & Bo Peng, 2016. "Multi-start iterated tabu search for the minimum weight vertex cover problem," Journal of Combinatorial Optimization, Springer, vol. 32(2), pages 368-384, August.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wsi:apjorx:v:23:y:2006:i:02:n:s0217595906000905. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Tai Tone Lim (email available below). General contact details of provider: http://www.worldscinet.com/apjor/apjor.shtml .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.