An Exact Algorithm for Minimum Weight Vertex Cover Problem in Large Graphs
- Resource Type
- Working Paper
- Authors
- Wang, Luzhi; Li, Chu-Min; Zhou, Junping; Jin, Bo; Yin, Minghao
- Source
- Subject
- Computer Science - Data Structures and Algorithms
Computer Science - Discrete Mathematics
- Language
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.