A PTAS for minimum weighted connected vertex cover $$P_3$$ problem in 3-dimensional wireless sensor networks

Given a connected and weighted graph (G=(V, E)) with each vertex v having a nonnegative weight w(v), the minimum weighted connected vertex cover (P_{3}) problem ((MWCVCP_{3})) is required to find a subset C of vertices of the graph with minimum total weight, such that each path with length 2 has at least one vertex in C, and moreover, the induced subgraph G[C] is connected. This kind of problem has many applications concerning wireless sensor networks and ad hoc networks. When homogeneous sensors are deployed into a three-dimensional space instead of a plane, the mathematical model for the sensor network is a unit ball graph instead of a unit disk graph. In this paper, we propose a new concept called weak c-local and give the first polynomial time approximation scheme (PTAS) for (MWCVCP_{3}) in unit ball graphs when the weight is smooth and weak c-local.