We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
PTAS for the minimum k-path connected vertex cover problem in unit disk graphs.
- Authors
Liu, Xianliang; Lu, Hongliang; Wang, Wei; Wu, Weili
- Abstract
In the Minimum k-Path Connected Vertex Cover Problem (M kPCVCP), we are given a connected graph G and an integer k ≥ 2, and are required to find a subset C of vertices with minimum cardinality such that each path with length k − 1 has a vertex in C, and moreover, the induced subgraph G[ C] is connected. M kPCVCP is a generalization of the minimum connected vertex cover problem and has applications in many areas such as security communications in wireless sensor networks. M kPCVCP is proved to be NP-complete. In this paper, we give the first polynomial time approximation scheme (PTAS) for M kPCVCP in unit disk graphs, for every fixed k ≥ 2.
- Subjects
POLYNOMIALS; ALGEBRA; APPROXIMATION theory; BERNOULLI polynomials; BERNSTEIN polynomials
- Publication
Journal of Global Optimization, 2013, Vol 56, Issue 2, p449
- ISSN
0925-5001
- Publication type
Article
- DOI
10.1007/s10898-011-9831-x