An improved algorithm for minimum connected dominating sets in ad hoc networks

作者：Yang Hong Wa; Yang Xiao Niu; Li Xin Feng; Lu Zhe Ming^*

来源：ICIC Express Letters, Part B: Applications , 2015, 6(1): 201-206.

• Breadth-first-search
• Connected Dominating Set
• Connected dominating set algorithms
• Disconnected graph
• Independent set
• Minimum connected dominating set
• Original algorithms
• Virtual backbone

Given a graph, a connected dominating set is a subset of vertices such that every vertex is either in the subset or adjacent to a vertex in the subset and the subgraph induced by the subset is connected. A minimum connected dominating set (MCDS) is such a subset with the smallest possible cardinality. MCDS is popularly used for constructing virtual backbones for broadcasting in ad hoc networks. In this paper, we add breath-first-search in Phase II of Alzoubi’s distributed connected dominating set algorithm. The improved algorithm can find MCDS in both connected and disconnected graphs while the original algorithm can only be applied to connected graphs.

• 出版日期2015
• 单位浙江大学