Date Added: Oct 2010
The dominating set problem is a fundamental problem in graph theory. Given a graph G, a dominating set of the graph is a set of nodes such that every node in G is either in the set or has a direct neighboring node in the set. This problem, along with its variations, such as the connected dominating set or the k-dominating set, play significant role in many distributed applications, especially in those running over networks that lack any predefined infrastructure. Examples include Mobile Ad-hoc NETworks (MANETs), Wireless Sensor Networks (WSNs), peer-to-peer networks, etc. The main application of dominating sets in such networks is to provide a virtual infrastructure, or overlay, in order to achieve scalability and efficiency.