A virtual backbone plays an important role in routing packets in a Wireless Sensor Network where a predefined infrastructure is absent. Some nodes of the network takes on additional responsibilities in an algorithmic framework to form the virtual backbone. A connected dominating set (CDS) can work as a virtual backbone in a wireless network. A dominating set of a graph is a subset of its vertices such that each node is either within that set or adjacent to one of the nodes present in that set. If the nodes within the dominating set are connected, then the dominating set is known as a connected dominating set. As the routing responsibilities lie only on the CDS nodes, we are interested in minimizing the CDS size. However, the construction of minimum CDS is an NP-Complete problem. In this dissertation, we first designed a new centralized degree-based greedy approximation algorithm, which constructs CDSs of smaller sizes in comparison with other existing algo- rithms. The proposed algorithm retains the current best approximation ratio and is also the most time efficient CDS construction algorithm. In our second work, we developed a novel distributed greedy approximation algorithm for CDS con- struction which reduces the CDS size effectively. Our simulation shows that this is the most size optimal distributed CDS construction algorithm with linear mes- sage complexity. The algorithm constructs the CDSs in lesser number of rounds in comparison to other degree-based algorithms. In a CDS, a node may fail or downgrade due to lack of its battery power or some other reason. In this situation, it is advantageous to repair the current CDS rather than reconstructing a fresh CDS. In our third work, we developed a distributed CDS maintenance algorithm which repairs the CDS by changing the role of only a few nodes. The proposed algorithm has linear time and message complexity. This CDS maintenance scheme handles the failure of both CDS and non-CDS nodes. To use our distributed CDS construction and maintenance algorithms each node needs its two-hop neighbours’ information.