2019/03/14 by Luzhi Wang, Chu-Min Li, Wang, Luzhi +7
Computer Science · #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.1903.05948
arxiv created 2019/03/14 · arxiv updated 2019/03/15
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.