TY - GEN
T1 - A convex-hull based algorithm to connect the maximal independent set in unit-disk graphs
AU - Chen, Dechang
AU - Mao, Xilong
AU - Fei, Xia
AU - Xing, Kai
AU - Liu, Fang
AU - Song, Min
PY - 2006
Y1 - 2006
N2 - In this paper we propose and analyze a localized convex-hull based algorithm to connect a maximal independent set. The cardinality of the resultant connected dominating set is at most 76 · opt + 19, where opt is the size of a minimum connected dominating set. To our knowledge, this is a dramatic improvement compared to the best published results in the same context [1,6]. Our algorithm plays an important rule in efficiently constructing a virtual backbone for ad hoc and sensor networks.
AB - In this paper we propose and analyze a localized convex-hull based algorithm to connect a maximal independent set. The cardinality of the resultant connected dominating set is at most 76 · opt + 19, where opt is the size of a minimum connected dominating set. To our knowledge, this is a dramatic improvement compared to the best published results in the same context [1,6]. Our algorithm plays an important rule in efficiently constructing a virtual backbone for ad hoc and sensor networks.
KW - Ad hoc and sensor networks
KW - Connected dominating set
KW - Maximal independent set
UR - http://www.scopus.com/inward/record.url?scp=33749668882&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33749668882&partnerID=8YFLogxK
U2 - 10.1007/11814856_35
DO - 10.1007/11814856_35
M3 - Conference contribution
AN - SCOPUS:33749668882
SN - 3540371893
SN - 9783540371892
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 363
EP - 370
BT - Wireless Algorithms, Systems, and Applications - First International Conference, WASA 2006, Proceedings
T2 - First International Conference on Wireless Algorithms, Systems, and Applications, WASA 2006
Y2 - 15 August 2006 through 17 August 2006
ER -