Title: Efficient Approximation Algorithm for Minimum Connected Dominating Set
Abstract: Finding a minimum connected dominating set for a network graph is of great importance in practical applications.However,how to search for it exactly is a NP-hard problem.This paper proposes a simple but efficient approximation heuristic algorithm for constructing a connected dominating set,which includes three stages,firstly assigning a rank for each node and forming an ordered list,then constructing a minimal independent set(MIS),and at last connecting the nodes in the MIS.Simulation experiments show the high efficiency of this algorithm in both execution time and results.
Publication Year: 2008
Publication Date: 2008-01-01
Language: en
Type: article
Access and Citation
Cited By Count: 2
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot