One of the critical issues in wireless sensor network is the design of a proper routing protocol. One
possible approach is utilizing a virtual infrastructure, which is a subset of sensors to connect all the sensors in the
network. Among the many virtual infrastructures, the connected dominating set is widely used. Since a small
connected dominating set can help to decrease the protocol overhead and energy consumption, it is preferable to
find a small sized connected dominating set. Although many algorithms have been suggested to construct a
minimum connected dominating set, there have been few exact approaches. In this paper, we suggest an
improved optimal algorithm for the minimum connected dominating set problem, and extensive computational
results showed that our algorithm outperformed the previous exact algorithms. Also, we suggest a new heuristic
algorithm to find the connected dominating set and computational results show that our algorithm is capable of
finding good quality solutions quite fast.