This paper introduces two new algorithms for the minimum connected dominating set (MCDS) problem with constraints applicable to wireless network design, based on simulated annealing and tabu search principles. Each algorithm is tested on a selection of random graphs and shown to produce significantly smaller connected dominating sets when compared to a number of established methods. The simulated annealing algorithm is found to favour large, sparse graphs while the tabu search heuristic prefers smaller dense instances. In conclusion, we consider the adaptation of these algorithms to hybrid techniques and comment on the possible use of hyper-heuristics.