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
2090222354 1534484868 1502920553 2127622665 2118005842
The dominating set problem asks for a small subset D of nodes in a graph such that every node is either in D or adjacent to a node in D. This problem arises in a number of distributed network applications, where it is important to locate a small number of centers in the network such that every node is nearby at least one center. Finding a dominating set of minimum size is NP-complete, and the best known approximation is logarithmic in the maximum degree of the graph and is provided by the same simple greedy approach that gives the well-known logarithmic approximation result for the closely related set cover problem.We describe and analyze new randomized distributed algorithms for the dominating set problem that run in polylogarithmic time, independent of the diameter of the network, and that return a dominating set of size within a logarithmic factor from optimal, with high probability. In particular, our best algorithm runs in O(log n log Δ) rounds with high probability, where n is the number of nodes, Δ is one plus the maximum degree of any node, and each round involves a constant number of message exchanges among any two neighbors; the size of the dominating set obtained is within O (log Δ) of the optimal in expectation and within O(log n) of the optimal with high probability. We also describe generalizations to the weighted case and the case of multiple covering requirements. This article presents a fast distributed algorithm to compute a smallk-dominating setD(for any fixedk) and to compute its induced graph partition (breaking the graph into radiuskclusters centered around the vertices ofD). The time complexity of the algorithm isO(klog*n). Smallk-dominating sets have applications in a number of areas, including routing with sparse routing tables, the design of distributed data structures, and center selection in a distributed network. The main application described in this article concerns a fast distributed algorithm for constructing a minimum-weight spanning tree (MST). On ann-vertex network of diameterd, the new algorithm constructs an MST in time, improving on previous results. In this paper we extend the lower bound technique by Linial for local coloring and maximal independent sets. We show that constant approximations to maximum independent sets on a ring require at least log-star time. More generally, the product of approximation quality and running time cannot be less than log-star. Using a generalized ring topology, we gain identical lower bounds for approximations to minimum dominating sets. Since our generalized ring topology is contained in a number of geometric graphs such as the unit disk graph, our bounds directly apply as lower bounds for quite a few algorithmic problems in wireless networking. Having in mind these and other results about local approximations of maximum independent sets and minimum dominating sets, one might think that the former are always at least as difficult to obtain as the latter. Conversely, we show that graphs exist, where a maximum independent set can be determined without any communication, while finding even an approximation to a minimum dominating set is as hard as in general graphs. 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. 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.