DocumentCode
854783
Title
Connected dominating sets in disk graphs with bidirectional links
Author
Thai, My T. ; Du, Ding-Zhu
Author_Institution
Dept. of Comput. Sci. & Eng., Minnesota Univ., Minneapolis, MN, USA
Volume
10
Issue
3
fYear
2006
fDate
3/1/2006 12:00:00 AM
Firstpage
138
Lastpage
140
Abstract
In this paper, we study the connected dominating set (CDS) problem in disk graphs. The CDS problem has a significant impact on an efficient design of routing protocols in wireless networks. This problem has been studied extensively in unit disk graphs, in which each node has the same transmission range. However, in wireless ad hoc networks, the transmission ranges of all nodes are not necessary equal. In this paper, we introduce the CDS problem in disk graphs and present a constant approximation algorithm which can be implemented as a distributed algorithm.
Keywords
ad hoc networks; distributed algorithms; graph theory; routing protocols; CDS problem; approximation algorithm; bidirectional link; connected dominating set; disk graph; distributed algorithm; routing protocol; wireless ad hoc network; Approximation algorithms; Distributed algorithms; Intelligent networks; Mobile ad hoc networks; Network topology; Routing protocols; Spine; Spread spectrum communication; Telecommunication traffic; Wireless networks;
fLanguage
English
Journal_Title
Communications Letters, IEEE
Publisher
ieee
ISSN
1089-7798
Type
jour
DOI
10.1109/LCOMM.2006.1603363
Filename
1603363
Link To Document