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

详细信息    查看全文

• 作者：Limin Wang ; Wenxue Du ; Zhao Zhang ; Xiaoyan Zhang
• 关键词：PTAS ; Connected vertex cover \(P_3\) ; Smooth weights ; Weak c ; local ; Unit ball graph
• 刊名：Journal of Combinatorial Optimization
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：33
• 期：1
• 页码：106-122
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Combinatorics; Convex and Discrete Geometry; Mathematical Modeling and Industrial Mathematics; Theory of Computation; Optimization; Operation Research/Decision Theory;
• 出版者：Springer US
• ISSN：1573-2886
• 卷排序：33

文摘

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.