Abstract: A new energy efficient heuristic algorithm is proposed for the minimum connected dominating set problem. The algorithm starts with an original solution containing all nodes of the network,and then reduces the size of the connected dominating set(CDS) by removing some redundant nodes using a heuristic policy until there are no redundant nodes.Both the centralized and distributed versions of this algorithm are discussed.The simulation results show that the presented algorithms are superior to other existing approaches in complexity and steady running time.