Abstract
A wireless ad-hoc network is a wireless, multihop network without an infrastructure. And due to the limited resources of hosts in the network, the resource utilization becomes more critical. As a result, construction of virtual backbones in wireless ad-hoc networks gets more attractive. In this paper, we present a distributed approximation scheme for minimum connected dominating sets in unit-disk graphs which can serve as a virtual backbone in the network. Our algorithm has the performance ratio of 7 and the message complexity of $O(n log n)$, which are the best among the schemes in the literature.
Cite this paper
@misc{min2003a,
title = {A Distributed Approximation for Minamum Connecting Dominated Sets in Wireless Networks},
author = {Manki Min and Raghuram Lanka and Xiao Huang and Ding‐Zhu Du},
howpublished = {University of Minnesota Digital Conservancy (University of Minnesota)},
year = {2003}
}