An Exact Algorithm for Minimum Vertex Cover Problem

Luzhi Wang, Shuli Hu, Mingyang Li and Junping Zhou
Additional contact information
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

Mathematics, 2019, vol. 7, issue 7, 1-8

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.

Keywords: vertex cover; branch-and-bound; MaxSAT; exact algorithm (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/7/7/603/pdf (application/pdf)
https://www.mdpi.com/2227-7390/7/7/603/ (text/html)

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

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().