Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Dominating set
Summary
In graph theory, a dominating set for a graph G is a subset D of its vertices, such that any vertex of G is either in D, or has a neighbor in D. The domination number γ(G) is the number of vertices in a smallest dominating set for G.
The dominating set problem concerns testing whether γ(G) ≤ K for a given graph G and input K; it is a classical NP-complete decision problem in computational complexity theory. Therefore it is believed that there may be no efficient algorithm that can compute γ(G) for all graphs G. However, there are efficient approximation algorithms, as well as efficient exact algorithms for certain graph classes.
Dominating sets are of practical interest in several areas. In wireless networking, dominating sets are used to find efficient routes within ad-hoc mobile networks. They have also been used in document summarization, and in designing secure systems for electrical grids.
Given an undirected graph G = (V, E), a subset of vertices is called a dominating set if for every vertex , there is a vertex such that .
Every graph has at least one dominating set: if the set of all vertices, then by definition D is a dominating set, since there is no vertex . A more interesting challenge is to find small dominating sets. The domination number of G is defined as: .
A connected dominating set is a dominating set that is also connected. If S is a connected dominating set, one can form a spanning tree of G in which S forms the set of non-leaf vertices of the tree; conversely, if T is any spanning tree in a graph with more than two vertices, the non-leaf vertices of T form a connected dominating set. Therefore, finding minimum connected dominating sets is equivalent to finding spanning trees with the maximum possible number of leaves.
A total dominating set (or strongly-dominating set) is a set of vertices such that all vertices in the graph, including the vertices in the dominating set themselves, have a neighbor in the dominating set. That is: for every vertex , there is a vertex such that .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.