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. 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.
    2. Foad Mahdavi Pajouh, 2020. "Minimum cost edge blocker clique problem," Annals of Operations Research, Springer, vol. 294(1), pages 345-376, November.
    3. 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.
    4. Filipa D. Carvalho & Maria Teresa Almeida, 2017. "The triangle k-club problem," Journal of Combinatorial Optimization, Springer, vol. 33(3), pages 814-846, April.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. Rota Bulò, Samuel & Pelillo, Marcello, 2017. "Dominant-set clustering: A review," European Journal of Operational Research, Elsevier, vol. 262(1), pages 1-13.
    11. 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.
    12. 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.
    13. Paweł Daniluk & Grzegorz Firlik & Bogdan Lesyng, 2019. "Implementation of a maximum clique search procedure on CUDA," Journal of Heuristics, Springer, vol. 25(2), pages 247-271, April.
    14. Lin, B.M.T. & Lu, C.Y. & Shyu, S.J. & Tsai, C.Y., 2008. "Development of new features of ant colony optimization for flowshop scheduling," International Journal of Production Economics, Elsevier, vol. 112(2), pages 742-755, April.
    15. Sebastian Lamm & Peter Sanders & Christian Schulz & Darren Strash & Renato F. Werneck, 2017. "Finding near-optimal independent sets at scale," Journal of Heuristics, Springer, vol. 23(4), pages 207-229, August.
    16. James T. Hungerford & Francesco Rinaldi, 2019. "A General Regularized Continuous Formulation for the Maximum Clique Problem," Management Science, INFORMS, vol. 44(4), pages 1161-1173, November.
    17. San Segundo, Pablo & Furini, Fabio & Álvarez, David & Pardalos, Panos M., 2023. "CliSAT: A new exact algorithm for hard maximum clique problems," European Journal of Operational Research, Elsevier, vol. 307(3), pages 1008-1025.
    18. Melisew Tefera Belachew & Nicolas Gillis, 2017. "Solving the Maximum Clique Problem with Symmetric Rank-One Non-negative Matrix Approximation," Journal of Optimization Theory and Applications, Springer, vol. 173(1), pages 279-296, April.
    19. Kristjan Reba & Matej Guid & Kati Rozman & Dušanka Janežič & Janez Konc, 2021. "Exact Maximum Clique Algorithm for Different Graph Types Using Machine Learning," Mathematics, MDPI, vol. 10(1), pages 1-14, December.
    20. Shuli Hu & Xiaoli Wu & Huan Liu & Yiyuan Wang & Ruizhi Li & Minghao Yin, 2019. "Multi-Objective Neighborhood Search Algorithm Based on Decomposition for Multi-Objective Minimum Weighted Vertex Cover Problem," Sustainability, MDPI, vol. 11(13), pages 1-21, July.

    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.