A Linear-Time and Linear-Space Algorithm for the Minimum Vertex Cover Problem on Giant Graphs

Proceedings of the International Symposium on Combinatorial Search, 10

Volume

Vol. 10 No. 1 (2017): Tenth Annual Symposium on Combinatorial Search

Extended Abstracts

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.

10.1609/socs.v8i1.18414