-
37浏览
-
0点赞
-
0收藏
-
0分享
-
0下载
-
0评论
-
引用
期刊论文
A simpler PTAS for connected k-path vertex cover in homogeneous wireless sensor network
Journal of Combinatorial Optimization ,2018,36():35–43 | 2018年03月28日 | doi.org/10.1007/s10878-018-0283-9
Because of its application in the field of security in wireless sensor networks, k-path vertex cover (VCPk) has received a lot of attention in recent years. Given a graph G=(V,E), a vertex set C⊆V is a k-path vertex cover (VCPk) of G if every path on k vertices has at least one vertex in C, and C is a connected k-path vertex cover of G (CVCPk) if furthermore the subgraph of G induced by C is connected. A homogeneous wireless sensor network can be modeled as a unit disk graph. This paper presents a new PTAS for MinCVCPk on unit disk graphs. Compared with previous PTAS given by Liu et al., our method not only simplifies the algorithm and reduces the time-complexity, but also simplifies the analysis by a large amount.
学者未上传该成果的PDF文件,请等待学者更新
本学者其他成果
同领域成果