An efficient connected dominating set algorithm in WSNs based on the induced tree of the crossed cube - Zhang, Jing; Xu, Li; Zhou, Shu-Ming; Wu, Wei; Ye, Xiucai (Zielona Góra: Uniwersytet Zielonogórski)
The connected dominating set (CDS) has become a well-known approach for constructing a virtual backbone in wireless sensor networks. Then traffic can forwarded by the virtual backbone and other nodes turn off their radios to save energy. Furthermore, a smaller CDS incurs fewer interference problems. However, constructing a minimum CDS is an NP-hard problem, and thus most researchers concentrate on how to derive approximate algorithms.
Keywords: wireless sensor networks; connected dominating set; induced tree; approximation algorithm; crossed cube