Efficient Approximation Algorithm for Minimum Connected Dominating Set
Fan Bing-quan · Journal of Chinese Computer Systems · 2008
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.