NuMWVC: A Novel Local Search for Minimum Weighted Vertex Cover Problem
Abstract
The minimum weighted vertex cover (MWVC) problem is a well known combinatorial optimization problem with important applications. This paper introduces a novel local search algorithm called NuMWVC for MWVC based on three ideas. First, four reduction rules are introduced during the initial construction phase. Second, the configuration checking with aspiration is proposed to reduce cycling problem. Moreover, a self-adaptive vertex removing strategy is proposed to save time.
Cite
Text
Li et al. "NuMWVC: A Novel Local Search for Minimum Weighted Vertex Cover Problem." AAAI Conference on Artificial Intelligence, 2018. doi:10.1609/AAAI.V32I1.12137Markdown
[Li et al. "NuMWVC: A Novel Local Search for Minimum Weighted Vertex Cover Problem." AAAI Conference on Artificial Intelligence, 2018.](https://mlanthology.org/aaai/2018/li2018aaai-numwvc/) doi:10.1609/AAAI.V32I1.12137BibTeX
@inproceedings{li2018aaai-numwvc,
title = {{NuMWVC: A Novel Local Search for Minimum Weighted Vertex Cover Problem}},
author = {Li, Ruizhi and Cai, Shaowei and Hu, Shuli and Yin, Minghao and Gao, Jian},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2018},
pages = {8107-8108},
doi = {10.1609/AAAI.V32I1.12137},
url = {https://mlanthology.org/aaai/2018/li2018aaai-numwvc/}
}