.png){kind=icon}
.png){kind=icon}
Return
Approximation algorithms for minimum weight connected 3-path vertex cover
.png){kind=icon}
PRE
AI
DOI：10.1016/j.amc.2018.11.045.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 (MinVCP(k)) has attracted a lot of researches in recent years. This paper studies the minimum weight connected VCPk problem (MinWCVCP(k)), 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 MinWCVCP(k) is set-cover-hard. We present two polynomial-time approximation algorithms for MinWCVCP(3). The first one is a greedy algorithm achieving approximation ratio 31n 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 delta(max) + 4 + ln 2, where delta(max) is the maximum degree of the graph. Considering the inapproximability of this problem, this ratio is asymptotically tight. (C) 2018 Elsevier Inc. All rights reserved.
Keywords:
Connected k-path vertex cover
Weight
Approximation algorithm
Non-submodular potential function
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
3.4
Papers:
2.3W
Citations:
3.3W
View more organizations