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

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▼]

@inproceedings{xu2017a,
    author = "Xu, Hong and Kumar, T. K. Satish and Koenig, Sven",
    title = "A Linear-Time and Linear-Space Algorithm for the Minimum Vertex Cover Problem on Giant Graphs",
    booktitle = "Proceedings of the 10th International Symposium on Combinatorial Search (SoCS)",
    year = "2017",
    url = "https://aaai.org/ocs/index.php/SOCS/SOCS17/paper/viewFile/15789/15080",
    pages = "173--174",
    customlinkposter = "http://files.hong.me/papers/xu2017a-poster.pdf",
    note = "extended abstract"
}

Abstract

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

[download]