Connected dominating set
Encyclopedia
In graph theory
, a connected dominated set and a maximum leaf spanning tree are two closely related structures defined on an undirected graph.
A minimum connected dominating set of a graph G is a connecting dominating set with the smallest possible cardinality among all connected dominating sets of G. The connected domination number of G is the number of vertices in the minimum connected dominating set.
Any spanning tree
T of a graph G has at least two leaves, vertices that have only one edge of T incident to them. A maximum leaf spanning tree is a spanning tree that has the largest possible number of leaves among all spanning trees of G. The max leaf number of G is the number of leaves in the maximum leaf spanning tree.
If D is a connected dominating set, then there exists a spanning tree
in G whose leaves include all vertices that are not in D: form a spanning tree of the subgraph induced by D, together with edges connecting each remaining vertex v that is not in D to a neighbor of v in D. This shows that
In the other direction, if T is any spanning tree in G, then the vertices of T that are not leaves form a connected dominating set of G. This shows that Putting these two inequalities together proves the equality
Therefore, in any graph, the sum of the connected domination number and the max leaf number equals the total number of vertices.
Computationally, this implies that finding the minimum dominating set is equally difficult to finding a maximum leaf spanning tree.
to test whether there exists a connected dominating set with size less than a given threshold, or equivalently to test whether there exists a spanning tree with at least a given number of leaves. Therefore, it is believed that the minimum connected dominating set problem and the maximum leaf spanning tree problem cannot be solved in polynomial time.
When viewed in terms of approximation algorithms, connected domination and maximum leaf spanning trees are not the same: approximating one to within a given approximation ratio is not the same as approximating the other to the same ratio.
There exists an approximation for the minimum connected dominating set that achieves a factor of , where Δ is the maximum degree of a vertex in G.
The maximum leaf spanning tree problem is MAX-SNP hard, implying that no polynomial time approximation scheme is likely. However, it can be approximated to within a factor of 2 in polynomial time.
for mobile ad-hoc networks. In this application, a small connected dominating set is used as a backbone for communications, and nodes that are not in this set communicate by passing messages through neighbors that are in the set.
The max leaf number has been employed in the development of fixed-parameter tractable algorithm
s: several NP-hard optimization problems may be solved in polynomial time for graphs of bounded max leaf number.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a connected dominated set and a maximum leaf spanning tree are two closely related structures defined on an undirected graph.
Definitions
A connected dominating set of a graph G is a set D of vertices with two properties:- Any node in D can reach any other node in D by a path that stays entirely within D. That is, D induces a connected subgraph of G.
- Every vertex in G either belongs to D or is adjacent to a vertex in D. That is, D is a dominating setDominating setIn graph theory, a dominating set for a graph G = is a subset D of V such that every vertex not in D is joined to at least one member of D by some edge...
of G.
A minimum connected dominating set of a graph G is a connecting dominating set with the smallest possible cardinality among all connected dominating sets of G. The connected domination number of G is the number of vertices in the minimum connected dominating set.
Any spanning tree
Spanning tree
Spanning tree can refer to:* Spanning tree , a tree which contains every vertex of a more general graph* Spanning tree protocol, a protocol for finding spanning trees in bridged networks...
T of a graph G has at least two leaves, vertices that have only one edge of T incident to them. A maximum leaf spanning tree is a spanning tree that has the largest possible number of leaves among all spanning trees of G. The max leaf number of G is the number of leaves in the maximum leaf spanning tree.
Complementarity
If d is the connected domination number of an n-vertex graph G, and l is its max leaf number, then the three quantities d, l, and n obey the simple equationIf D is a connected dominating set, then there exists a spanning tree
Spanning tree
Spanning tree can refer to:* Spanning tree , a tree which contains every vertex of a more general graph* Spanning tree protocol, a protocol for finding spanning trees in bridged networks...
in G whose leaves include all vertices that are not in D: form a spanning tree of the subgraph induced by D, together with edges connecting each remaining vertex v that is not in D to a neighbor of v in D. This shows that
In the other direction, if T is any spanning tree in G, then the vertices of T that are not leaves form a connected dominating set of G. This shows that Putting these two inequalities together proves the equality
Therefore, in any graph, the sum of the connected domination number and the max leaf number equals the total number of vertices.
Computationally, this implies that finding the minimum dominating set is equally difficult to finding a maximum leaf spanning tree.
Algorithms
It is NP-completeNP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
to test whether there exists a connected dominating set with size less than a given threshold, or equivalently to test whether there exists a spanning tree with at least a given number of leaves. Therefore, it is believed that the minimum connected dominating set problem and the maximum leaf spanning tree problem cannot be solved in polynomial time.
When viewed in terms of approximation algorithms, connected domination and maximum leaf spanning trees are not the same: approximating one to within a given approximation ratio is not the same as approximating the other to the same ratio.
There exists an approximation for the minimum connected dominating set that achieves a factor of , where Δ is the maximum degree of a vertex in G.
The maximum leaf spanning tree problem is MAX-SNP hard, implying that no polynomial time approximation scheme is likely. However, it can be approximated to within a factor of 2 in polynomial time.
Applications
Connected dominating set are useful in the computation of routingRouting
Routing is the process of selecting paths in a network along which to send network traffic. Routing is performed for many kinds of networks, including the telephone network , electronic data networks , and transportation networks...
for mobile ad-hoc networks. In this application, a small connected dominating set is used as a backbone for communications, and nodes that are not in this set communicate by passing messages through neighbors that are in the set.
The max leaf number has been employed in the development of fixed-parameter tractable algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s: several NP-hard optimization problems may be solved in polynomial time for graphs of bounded max leaf number.