Improving Construction for Connected Dominating Set with Steiner Tree in Wireless Sensor Networks |
| |
Authors: | Manki Min Hongwei Du Xiaohua Jia Christina Xiao Huang Scott C.-H. Huang Weili Wu |
| |
Affiliation: | (1) Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN 55455, USA;(2) Department of Computer Science, City University of Hong Kong, Kowloon Tong, Hong Kong;(3) 3M Center, Building 0235-03-F-08. St. Paul, MN 55144, USA;(4) Department of Computer Science, University of Texas at Dallas, Richardson, Tx, 75083 |
| |
Abstract: | The connected dominating set plays an important role in ad hoc wireless networking. Many constructions for approximating the minimum connected dominating set have been proposed in the literature. In this paper, we propose a new one with Steiner tree, which produces approximation solution within a factor of 6.8 from optimal. This approximation algorithm can also be implemented distributedly. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|