A PTAS for minimum connected dominating set in 3-dimensional Wireless sensor networks |
| |
Authors: | Zhao Zhang Xiaofeng Gao Weili Wu Ding-Zhu Du |
| |
Institution: | 1.College of Mathematics and System Sciences,Xinjiang University,Urumqi,People’s Republic of China;2.Department of Computer Science,University of Texas at Dallas,Richardson,USA |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|