A multi-start iterated greedy algorithm for the minimum weight vertex cover P3 problem

Wenjie Zhang, Jianhua Tu and Lidong Wu

Applied Mathematics and Computation, 2019, vol. 349, issue C, 359-366

Abstract: Given a vertex-weighted graph G=(V,E) and a positive integer k ≥ 2, the minimum weight vertex cover Pk (MWVCPk) problem is to find a vertex subset F ⊆ V with minimum total weight such that every path of order k in G contains at least one vertex in F. For any integer k ≥ 2, the MWVCPk problem for general graphs is NP-hard. In this paper, we restrict our attention to the MWVCP3 problem and present a multi-start iterated greedy algorithm to solve the MWVCP3 problem. The experiments are carried out on randomly generated instances with up to 1000 vertices and 250000 edges. Our work is the first one to adopt heuristic algorithms to solve the MWVCP3 problem, and the experimental results show that our algorithm performs reasonably well in practice.

Keywords: Iterated greedy algorithm; Minimum weight vertex cover P3 problem; Heuristic algorithms; Combinatorial optimization problems (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300318311287
Full text for ScienceDirect subscribers only

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:eee:apmaco:v:349:y:2019:i:c:p:359-366

DOI: 10.1016/j.amc.2018.12.067

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().