首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号