LAUSR

Because of its application in the field of security in wireless sensor networks, k-path vertex cover ($$\hbox {VCP}_k$$VCPk) has received a lot of attention in recent years. Given a graph $$G=(V,E)$$G=(V,E), a vertex set $$C\subseteq V$$C⊆V is a k-path vertex cover ($$\hbox {VCP}_k$$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 ($$\hbox {CVCP}_k$$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 $$\hbox {MinCVCP}_k$$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.