Algorithmic Aspects for Total Connected Dominating Sets in Mobile Ad Hoc Wireless Networks
In wireless ad hoc networks, there is no fixed or pre-defined infrastructure. Nodes in wireless networks communicate via a shared medium, either through a single hop or multi-hops. Although there is no physical backbone infrastructure, a virtual backbone can be formed by constructing a Total Connected Dominating Set (TCDS). Given an undirected graph G = (V; E). A matching in G is a subset M of edges of E such that no two edges in M are adjacent. A matching M in G is called a perfect matching if every vertex of G is incident to some edge in M.