An Exact Algorithm for Minimum Weight Vertex Cover Problem in Large Graphs
classification
💻 cs.DS
cs.DM
keywords
algorithmcovergraphslargeminimumvertexweightbmwvc
Add this Pith Number to your LaTeX paper
What is a Pith Number?\usepackage{pith}
\pithnumber{62OHQ3SX}
Prints a linked pith:62OHQ3SX badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more
read the original abstract
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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.