NuMWVC: A novel local search for minimum weighted vertex cover problem

Ruizhi Li, Shuli Hu, Shaowei Cai, Jian Gao, Yiyuan Wang and Minghao Yin

Journal of the Operational Research Society, 2020, vol. 71, issue 9, 1498-1509

Abstract: The problem of finding a minimum weighted vertex cover (MWVC) in a graph is a well-known combinatorial optimisation problem with important applications. This article 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, a strategy called configuration checking with aspiration, which aims for reducing cycling in local search, is proposed for MWVC for the first time. Moreover, a self-adaptive vertex removing strategy is proposed to save time spent on searching solutions for which the quality is likely far from optimality. Experimental results show that NuMWVC outperforms state-of-the-art local search algorithms for MWVC on the standard benchmarks, massive graphs and real-world problem (map labeling problem) instances.

Date: 2020
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/01605682.2019.1621218 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tjorxx:v:71:y:2020:i:9:p:1498-1509

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/tjor20

DOI: 10.1080/01605682.2019.1621218

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald

More articles in Journal of the Operational Research Society from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().