A k-dominating set is a set D of nodes of a graph such that, for each node v, there exists a node wD at distance at most k from v. Our aim is the deterministic distributed construction of small T-dominating sets in time T in networks modelled as undirected n-node graphs and under the LOCAL communication model.For any positive integer T, if b is the size of a pairwise disjoint collection of balls of radii at least T in a graph, then b is an obvious lower bound on the size of a T-dominating set. Our first result shows that, even on rings, it is impossible to construct a T-dominating set of size s asymptotically b (i.e.,such that sb1) in time T.In the range of time T(logn), the size of a T-dominating set turns out to be very sensitive to multiplicative constants in running time. Indeed, it follows from Kutten and Peleg (1998), that for time T=logn with large constant , it is possible to construct a T-dominating set whose size is a small fraction of n. By contrast, we show that, for time T=logn for small constant , the size of a T-dominating set must be a large fraction of n.Finally, when To(logn), the above lower bound implies that, for any constant x<1, it is impossible to construct a T-dominating set of size smaller than xn, even on rings. On the positive side, we provide an algorithm that constructs a T-dominating set of size n(T) on all graphs.
In @cite_11 , the authors studied how fast a capacitated minimum dominating set can be distributedly constructed. They showed that, for general graphs, every distributed algorithm achieving a non-trivial approximation ratio (even for uniform capacities) must have a time complexity that essentially grows linearly with the network diameter. In @cite_10 @cite_13 , randomized distributed solutions for dominating set approximation were presented. In @cite_6 the authors prove that, for any @math -approximation of the minimum dominating set or maximum independent set on Unit Disk Graphs, the time @math of finding this approximation must satisfy @math . The paper most closely related to the present work is @cite_3 . The authors present a distributed algorithm to find a @math -dominating set of size at most @math in arbitrary @math -node graphs. Their algorithm runs in time @math in the @math model.
@cite_10 @cite_3 @cite_6 @cite_13 @cite_11
2687257225 2118005842 2127622665 2169848785
We study local, distributed algorithms for the capacitated minimum dominating set (CapMDS) problem, which arises in various distributed network applications. Given a network graph G=(V,E), and a capacity cap(v)∈ℕ for each node v∈V, the CapMDS problem asks for a subset S⊆V of minimal cardinality, such that every network node not in S is covered by at least one neighbor in S, and every node v∈S covers at most cap(v) of its neighbors. We prove that in general graphs and even with uniform capacities, the problem is inherently non-local, i.e., every distributed algorithm achieving a non-trivial approximation ratio must have a time complexity that essentially grows linearly with the network diameter. On the other hand, if for some parameter e>0, capacities can be violated by a factor of 1+e, CapMDS becomes much more local. Particularly, based on a novel distributed randomized rounding technique, we present a distributed bi-criteria algorithm that achieves an O(log Δ)-approximation in time O(log 3 n+log (n) e), where n and Δ denote the number of nodes and the maximal degree in G, respectively. Finally, we prove that in geometric network graphs typically arising in wireless settings, the uniform problem can be approximated within a constant factor in logarithmic time, whereas the non-uniform problem remains entirely non-local. We study local, distributed algorithms for the capacitated minimum dominating set (CapMDS) problem, which arises in various distributed network applications. Given a network graph G = (V,E), and a capacity cap(v) ∈ N for each node v ∈ V , the CapMDS problem asks for a subset S ⊆ V of minimal cardinality, such that every network node not in S is covered by at least one neighbor in S, and every node v ∈ S covers at most cap(v) of its neighbors. We prove that in general graphs and even with uniform capacities, the problem is inherently non-local, i.e., every distributed algorithm achieving a non-trivial approximation ratio must have a time complexity that essentially grows linearly with the network diameter. On the other hand, if for some parameter e > 0, capacities can be violated by a factor of 1 + e, CapMDS becomes much more local. Particularly, based on a novel distributed randomized rounding technique, we present a distributed bi-criteria algorithm that achieves an O(log Δ)-approximation in time O(log3n + log(n) e), where n and Δ denote the number of nodes and the maximal degree in G, respectively. Finally, we prove that in geometric network graphs typically arising in wireless settings, the uniform problem can be approximated within a constant factor in logarithmic time, whereas the non-uniform problem remains entirely non-local. Finding a small dominating set is one of the most fundamental problems of traditional graph theory. In this paper, we present a new fully distributed approximation algorithm based on LP relaxation techniques. For an arbitrary parameter k and maximum degree Δ, our algorithm computes a dominating set of expected size O(kΔ2 k log Δ|DSOPT|) in O(k2) rounds where each node has to send O(k2Δ) messages of size O(logΔ). This is the first algorithm which achieves a non-trivial approximation ratio in a constant number of rounds. The dominating set problem in graphs asks for a minimum size subset of vertices with the following property: each vertex is required to be either in the dominating set, or adjacent to some vertex in the dominating set. We focus on the related question of finding a connected dominating set of minimum size, where the graph induced by vertices in the dominating set is required to be connected as well. This problem arises in network testing, as well as in wireless communication. Two polynomial time algorithms that achieve approximation factors of 2H(Δ)+2 and H(Δ)+2 are presented, where Δ is the maximum degree and H is the harmonic function. This question also arises in relation to the traveling tourist problem, where one is looking for the shortest tour such that each vertex is either visited or has at least one of its neighbors visited. We also consider a generalization of the problem to the weighted case, and give an algorithm with an approximation factor of (cn+1) n where cn ln k is the approximation factor for the node weighted Steiner tree problem (currently cn = 1.6103 ). We also consider the more general problem of finding a connected dominating set of a specified subset of vertices and provide a polynomial time algorithm with a (c+1) H(Δ) +c-1 approximation factor, where c is the Steiner approximation ratio for graphs (currently c = 1.644 ).