On approximation algorithms of k -connected m -dominating sets in disk graphs

Connected Dominating Set (CDS) has been proposed as the virtual backbone to alleviate the broadcasting storm in wireless ad hoc networks. Most recent research has extensively focused on the construction of 1-Connected 1-Dominating Set (1-CDS) in homogeneous networks. However, the nodes in the CDS ne...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2007-10, Vol.385 (1), p.49-59
Main Authors: Thai, My T., Zhang, Ning, Tiwari, Ravi, Xu, Xiaochun
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Computer science
control theory
systems
Computer systems performance. Reliability
Connected dominating set
Disk graphs
Exact sciences and technology
Fault tolerance
Information retrieval. Graph
Miscellaneous
Software
Theoretical computing
Virtual backbone
Wireless ad hoc network
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Connected Dominating Set (CDS) has been proposed as the virtual backbone to alleviate the broadcasting storm in wireless ad hoc networks. Most recent research has extensively focused on the construction of 1-Connected 1-Dominating Set (1-CDS) in homogeneous networks. However, the nodes in the CDS need to carry other node’s traffic and nodes in wireless networks are subject to failure. Therefore, it is desirable to construct a fault tolerant CDS. In this paper, we study a general fault tolerant CDS problem, called k -Connected m -Dominating Set ( k - m -CDS), in heterogeneous networks. We first present two approximation algorithms for 1- m -CDS and k - k -CDS problems. Using disk graphs to model heterogeneous networks, we show that our algorithms have a constant approximation ratio. Based on these two algorithms, we further develop a general algorithm for k - m -CDS. We also provide an interesting analysis for a special case of k - m -CDS, where k = m + 1 .
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2007.05.025