A simpler PTAS for connected <Emphasis Type="Italic">k</Emphasis>-path vertex cover in homogeneous wireless sensor network |
| |
Authors: | Lina Chen Xiaohui Huang Zhao Zhang |
| |
Institution: | 1.College of Mathematics Physics and Information Engineering,Zhejiang Normal University,Jinhua,China;2.Library and Information Center,Zhejiang Normal University,Jinhua,China |
| |
Abstract: | Because of its application in the field of security in wireless sensor networks, k-path vertex cover (\(\hbox {VCP}_k\)) has received a lot of attention in recent years. Given a graph \(G=(V,E)\), a vertex set \(C\subseteq V\) is a k-path vertex cover (\(\hbox {VCP}_k\)) 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 (\(\hbox {CVCP}_k\)) 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 \(\hbox {MinCVCP}_k\) 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|