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

On approximation algorithms of k-connected m-dominating sets in disk graphs,10.1016/j.tcs.2007.05.025,Theoretical Computer Science,My T. Thai,Ning Zha

On approximation algorithms of k-connected m-dominating sets in disk graphs   (Citations: 18)
BibTex | RIS | RefWorks Download
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.
Journal: Theoretical Computer Science - TCS , vol. 385, no. 1-3, pp. 49-59, 2007
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: