Title :
A New Greedy Algorithm for D-Hop Connected Dominating Set
Author :
Xianyue Li ; Xiaofeng Gao ; Chenxia Zhao
Author_Institution :
Sch. of Math. & Stat., Lanzhou Univ., Lanzhou, China
Abstract :
In this paper, we consider the problem how to interconnect an obtained d-hop MIS into a d-hop CDS. Firstly, we deal with a simple case d = 2 and present a greedy algorithm. Using this method, we can obtain a 2-hop CDS with approximation ratio min{3β,2β+2+2H (β-1)}, where β is the ratio of 2-hop MIS with 2-hop CDS and H (·) is the harmonic function. This ratio is better than the ratio using spanning tree method. Finally, we generalize the algorithm for general case.
Keywords :
approximation theory; greedy algorithms; trees (mathematics); 2-hop CDS; 2-hop MIS; approximation ratio; connected dominating set; d-hop CDS; d-hop MIS; d-hop connected dominating set; greedy algorithm; harmonic function; spanning tree method; Ad hoc networks; Algorithm design and analysis; Approximation algorithms; Approximation methods; Greedy algorithms; Optimized production technology; Silicon; approximation algorithm; connected dominating set; greedy strategy; multi-hop virtual back-bone;
Conference_Titel :
Mobile Ad-hoc and Sensor Networks (MSN), 2014 10th International Conference on
DOI :
10.1109/MSN.2014.14
