 Approximation algorithms for minimum weight connected 3-path vertex coverYingli Ran, Zhao Zhang, Xiaohui Huang, Xiaosong Li and Ding-Zhu Du Applied Mathematics and Computation, 2019, vol. 347, issue C, 723-733 Abstract: A k-path vertex cover (VCPk) is a vertex set C of graph G such that every path of G on k vertices has at least one vertex in C. Because of its background in keeping data integrality of a network, minimum VCPk problem (MinVCPk) has attracted a lot of researches in recent years. This paper studies the minimum weight connected VCPk problem (MinWCVCPk), in which every vertex has a weight and the VCPk found by the algorithm induces a connected subgraph and has the minimum weight. It is known that MinWCVCPk is set-cover-hard. We present two polynomial-time approximation algorithms for MinWCVCP3. The first one is a greedy algorithm achieving approximation ratio 3ln n. The difficulty lies in its analysis dealing with a non-submodular potential function. The second algorithm is a 2-stage one, finding a VCP3 in the first stage and then adding more vertices for connection. We show that its approximation ratio is at most lnδmax+4+ln2, where δmax is the maximum degree of the graph. Considering the inapproximability of this problem, this ratio is asymptotically tight. Keywords: Connected k-path vertex cover; Weight; Approximation algorithm; Non-submodular potential function (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:347:y:2019:i:c:p:723-733 DOI: 10.1016/j.amc.2018.11.045 Access Statistics for this article Applied Mathematics and Computation is currently edited by Theodore Simos More articles in Applied Mathematics and Computation from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.