.png){kind=icon}
返回
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}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
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.
Keyword:
Connected k-path vertex cover
Weight
Approximation algorithm
Non-submodular potential function
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
3.4
论文数:
2.3W
被引数:
3.3W
机构
查看更多机构
引用论文
.png){kind=icon}
没有更多内容