PTAS for Minimum k-Path Connected Vertex Cover in Growth-Bounded Graphs

摘要

In the paper, we present a polynomial-time approximation scheme (PTAS) for the minimum k-path connected vertex cover (MkPCVC) problem , which can be used to solve security problems in wireless sensor networks (WSNs), under fixed k≥2. In contrast to previously known approximation schemes for MkPCVC problem, our approach does not need location data of the vertices, and it can be applied to growth-bounded graphs. For any ε_1>0, the algorithm returns a (1+ε_1)-approximation MkPCVC. We have proved the correctness and performance of the algorithm and shown its runtime is rn~(O(f(r))), where f(r) is a polynomial function, r = O((1/ε)?ln(1/ε)) and ε is only dependent on k and ε_1.