# An Exact Algorithm for Minimum Weight Vertex Cover Problem in Large Graphs

arXiv: https://arxiv.org/abs/1903.05948 · HTML: https://mlsanity.com/paper/1903.05948/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Mar 2019.

## Built on by (most cited first, 1 of 1)

- [GOODAT: Towards Test-time Graph Out-of-Distribution Detection](https://mlsanity.com/paper/2401.06176/) (2024)

## Abstract (arXiv)

This paper proposes a novel branch-and-bound(BMWVC) algorithm to exactly solve the minimum weight vertex cover problem (MWVC) in large graphs. The original contribution is several new graph reduction rules, allowing to reduce a graph G and the time needed to find a minimum weight vertex cover in G. Experiments on large graphs from real-world applications show that the reduction rules are effective and the resulting BMWVC algorithm outperforms relevant exact and heuristic MWVC algorithms.