Hong Xu, T. K. Satish Kumar, and Sven Koenig. A linear-time and linear-space algorithm for the minimum vertex cover problem on giant graphs. In Proceedings of the 10th International Symposium on Combinatorial Search (SoCS), 173–174. 2017. extended abstract. URL: https://aaai.org/ocs/index.php/SOCS/SOCS17/paper/viewFile/15789/15080.
[full text] [poster] [BibTeX▼]


In this paper, we develop the message passing based linear-time and linear-space MVC algorithm (MVC-MPL) for solving the minimum vertex cover (MVC) problem. MVC-MPL is based on heuristics derived from a theoretical analysis of message passing algorithms in the context of belief propagation. We show that MVC-MPL produces smaller vertex covers than other linear-time and linear-space algorithms.

Full Text

Your browser does not support viewing the PDF file inline. Please click the link below to download the file.