您当前所在位置: 首页 > 学者

张昭

  • 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

URL:https://link.springer.com/article/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文件,请等待学者更新

我要评论

全部评论 0

本学者其他成果

    同领域成果