IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v7y2019i7p603-d246269.html
   My bibliography  Save this article

An Exact Algorithm for Minimum Vertex Cover Problem

Author

Listed:
  • Luzhi Wang

    (School of Computer Science and Information Technology, Northeast Normal University, Changchun 130117, China)

  • Shuli Hu

    (School of Computer Science and Information Technology, Northeast Normal University, Changchun 130117, China)

  • Mingyang Li

    (School of Computer Science and Information Technology, Northeast Normal University, Changchun 130117, China)

  • Junping Zhou

    (School of Computer Science and Information Technology, Northeast Normal University, Changchun 130117, China)

Abstract

In this paper, we propose a branch-and-bound algorithm to solve exactly the minimum vertex cover (MVC) problem. Since a tight lower bound for MVC has a significant influence on the efficiency of a branch-and-bound algorithm, we define two novel lower bounds to help prune the search space. One is based on the degree of vertices, and the other is based on MaxSAT reasoning. The experiment confirms that our algorithm is faster than previous exact algorithms and can find better results than heuristic algorithms.

Suggested Citation

  • Luzhi Wang & Shuli Hu & Mingyang Li & Junping Zhou, 2019. "An Exact Algorithm for Minimum Vertex Cover Problem," Mathematics, MDPI, vol. 7(7), pages 1-8, July.
    • Handle: RePEc:gam:jmathe:v:7:y:2019:i:7:p:603-:d:246269
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/7/7/603/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/7/7/603/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Wu, Qinghua & Hao, Jin-Kao, 2015. "A review on algorithms for maximum clique problems," European Journal of Operational Research, Elsevier, vol. 242(3), pages 693-709.
    2. Shyong Shyu & Peng-Yeng Yin & Bertrand Lin, 2004. "An Ant Colony Optimization Algorithm for the Minimum Weight Vertex Cover Problem," Annals of Operations Research, Springer, vol. 131(1), pages 283-304, October.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Seyedmohammadhossein Hosseinian & Dalila B. M. M. Fontes & Sergiy Butenko, 2020. "A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 747-762, July.
    2. Laurent, Monique & Vargas, Luis Felipe, 2022. "Finite convergence of sum-of-squares hierarchies for the stability number of a graph," Other publications TiSEM 3998b864-7504-4cf4-bc1d-f, Tilburg University, School of Economics and Management.
    3. Lehouillier, Thibault & Omer, Jérémy & Soumis, François & Desaulniers, Guy, 2017. "Two decomposition algorithms for solving a minimum weight maximum clique model for the air conflict resolution problem," European Journal of Operational Research, Elsevier, vol. 256(3), pages 696-712.
    4. Foad Mahdavi Pajouh, 2020. "Minimum cost edge blocker clique problem," Annals of Operations Research, Springer, vol. 294(1), pages 345-376, November.
    5. Zhou, Yi & Lin, Weibo & Hao, Jin-Kao & Xiao, Mingyu & Jin, Yan, 2022. "An effective branch-and-bound algorithm for the maximum s-bundle problem," European Journal of Operational Research, Elsevier, vol. 297(1), pages 27-39.
    6. Zhou, Yi & Hao, Jin-Kao & Goëffon, Adrien, 2017. "PUSH: A generalized operator for the Maximum Vertex Weight Clique Problem," European Journal of Operational Research, Elsevier, vol. 257(1), pages 41-54.
    7. Oleksandra Yezerska & Sergiy Butenko & Vladimir L. Boginski, 2018. "Detecting robust cliques in graphs subject to uncertain edge failures," Annals of Operations Research, Springer, vol. 262(1), pages 109-132, March.
    8. Lin Chen & Jin Peng & Bo Zhang & Shengguo Li, 2017. "Uncertain programming model for uncertain minimum weight vertex covering problem," Journal of Intelligent Manufacturing, Springer, vol. 28(3), pages 625-632, March.
    9. Zhang, Wenjie & Tu, Jianhua & Wu, Lidong, 2019. "A multi-start iterated greedy algorithm for the minimum weight vertex cover P3 problem," Applied Mathematics and Computation, Elsevier, vol. 349(C), pages 359-366.
    10. Filipa D. Carvalho & Maria Teresa Almeida, 2017. "The triangle k-club problem," Journal of Combinatorial Optimization, Springer, vol. 33(3), pages 814-846, April.
    11. Zhou, Yi & Rossi, André & Hao, Jin-Kao, 2018. "Towards effective exact methods for the Maximum Balanced Biclique Problem in bipartite graphs," European Journal of Operational Research, Elsevier, vol. 269(3), pages 834-843.
    12. 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.
    13. Pedro Pinacho-Davidson & Christian Blum, 2020. "Barrakuda : A Hybrid Evolutionary Algorithm for Minimum Capacitated Dominating Set Problem," Mathematics, MDPI, vol. 8(11), pages 1-26, October.
    14. Yang Wang & Jin-Kao Hao & Fred Glover & Zhipeng Lü & Qinghua Wu, 2016. "Solving the maximum vertex weight clique problem via binary quadratic programming," Journal of Combinatorial Optimization, Springer, vol. 32(2), pages 531-549, August.
    15. Luciano Ferreira Cruz & Flavia Bernardo Pinto & Lucas Camilotti & Angelo Marcio Oliveira Santanna & Roberto Zanetti Freire & Leandro Santos Coelho, 2022. "Improved multiobjective differential evolution with spherical pruning algorithm for optimizing 3D printing technology parametrization process," Annals of Operations Research, Springer, vol. 319(2), pages 1565-1587, December.
    16. Zhong, Haonan & Mahdavi Pajouh, Foad & A． Prokopyev, Oleg, 2023. "On designing networks resilient to clique blockers," European Journal of Operational Research, Elsevier, vol. 307(1), pages 20-32.
    17. Yuan Sun & Andreas Ernst & Xiaodong Li & Jake Weiner, 2021. "Generalization of machine learning for problem reduction: a case study on travelling salesman problems," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(3), pages 607-633, September.
    18. Wang, Yang & Wu, Qinghua & Glover, Fred, 2017. "Effective metaheuristic algorithms for the minimum differential dispersion problem," European Journal of Operational Research, Elsevier, vol. 258(3), pages 829-843.
    19. Rota Bulò, Samuel & Pelillo, Marcello, 2017. "Dominant-set clustering: A review," European Journal of Operational Research, Elsevier, vol. 262(1), pages 1-13.
    20. Li, Chu-Min & Liu, Yanli & Jiang, Hua & Manyà, Felip & Li, Yu, 2018. "A new upper bound for the maximum weight clique problem," European Journal of Operational Research, Elsevier, vol. 270(1), pages 66-77.

    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:gam:jmathe:v:7:y:2019:i:7:p:603-:d:246269. 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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    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.