-
4浏览
-
0点赞
-
0收藏
-
0分享
-
0下载
-
0评论
-
引用
期刊论文
A PTAS for minimum connected dominating set in 3-dimensional Wireless sensor networks
Journal of Global Optimization,2008,45():451–458 | 2008年12月14日 | doi.org/10.1007/s10898-008-9384-9
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. It is known that for the minimum connected dominating set in unit disk graph, there is a polynomial time approximation scheme (PTAS). However, that construction cannot be extended to obtain a PTAS for unit ball graph. In this paper, we will introduce a new construction, which gives not only a PTAS for the minimum connected dominating set in unit ball graph, but also improves running time of PTAS for unit disk graph.
学者未上传该成果的PDF文件,请等待学者更新
本学者其他成果
同领域成果