In wireless networks, energy is a precious resource since each node has a limited power source. To extend the lifetime of multi-hop wireless networks, it is essential to have an efficient routing scheme. It is known that by employing a virtual backbone in a wireless network, the efficiency of any routing scheme for the network can be improved. A smaller virtual backbone incurs less maintenance overhead. For this reason, many people used the minimum Connected Dominating Set (CDS) problem, which is a well-known NP-hard problem, to abstract the problem of computing quality virtual backbones in wireless networks. In Chapter 2, Chapter 3, and Chapter 4, we improve the existing results in this area in several aspects. In addition, two 3-D wireless network clustering problems using minimum number of supernodes are investigated in Chapter 5. |