%0 Journal Article
%A FENG Wangsen
%A CHEN Ping
%A ZHANG Bei
%A MA Hao
%T Approximating 2-Connected k-Dominating Fault-Tolerant Virtual Backbone
%D 2009
%R
%J Acta Scientiarum Naturalium Universitatis Pekinensis
%P 421-425
%V 45
%N 3
%X Because of the inherent node (link) failures in wireless networks, virtual backbones should be fault-tolerant. Fault-tolerant virtual backbones were modeled as 2-connected k-dominating sets. An approximation algorithm was designed to find a 2-connected k-dominating virtual backbone in wireless ad-hoc networks by analyzing the properties of maximal independent sets in unit disk graphs and the block-cutvertex tree structure of connected graphs. The time complexity and the performance ratio of the algorithm were analyzed and proved to be a constant, respectively.
%U http://xbna.pku.edu.cn/EN/abstract/article_2059.shtml