Title: An Algorithm for Searching a Connected Dominating Set with Minimum Total-Edge-Weight in a Graph
Abstract: A new mathematical problem, namely searching a connected dominating set (CDS) with the minimum total edge weight in an edge-weighted graph which can provide a better mathematical model for wireless networks, has been brought forward from the design of wireless networks. To solve this problem, an approximation algorithm with polynomial-time complexity is proposed in this paper. The simulation results demonstrate the effectiveness of the proposed algorithm, and the results also show that the approximation ratio of the proposed algorithm is up to 0.7.
Publication Year: 2012
Publication Date: 2012-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot