Abstract
In this paper we consider a generalization of the classical dominating set problem to the k-tuple dominating set problem (kMDS). For any positive integer k, we look for a smallest subset of vertices D ⊆ V with the property that every vertex in V\D is adjacent to at least k vertices of D. We are interested in the distributed complexity of this problem in the model, where the nodes have no identifiers. The most challenging case is when k = 2, and for this case we propose a distributed local algorithm, which runs in a constant number of rounds, yielding a 7-approximation in the class of planar graphs. On the other hand, in the class of algorithms in which every vertex uses only its degree and the degree of its neighbors to make decisions, there is no algorithm providing a (5 -ϵ)-approximation of the 2MDS problem. In addition, we show a lower bound of (4 - ϵ) for the 2MDS problem even if unique identifiers are allowed.
For k ≥ 3, we show that for the problem kMDS in planar graphs, a trivial algorithm yields a k/(k - 2)-approximation. In the model with unique identifiers this, surprisingly, is optimal for k = 3, 4, 5, and 6, as we provide a matching lower bound.
Original language | English (US) |
---|---|
Title of host publication | Principles of Distributed Systems - 18th International Conference, OPODIS 2014, Proceedings |
Editors | Marcos K. Aguilera, Leonardo Querzoni, Marc Shapiro |
Publisher | Springer Verlag |
Pages | 49-59 |
Number of pages | 11 |
ISBN (Electronic) | 9783319144719 |
DOIs | |
State | Published - Jan 1 2014 |
Event | 18th International Conference on Principles of Distributed Systems, OPODIS 2014 - Cortina d’Ampezzo, Italy Duration: Dec 16 2014 → Dec 19 2014 |
Publication series
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 8878 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Other
Other | 18th International Conference on Principles of Distributed Systems, OPODIS 2014 |
---|---|
Country/Territory | Italy |
City | Cortina d’Ampezzo |
Period | 12/16/14 → 12/19/14 |
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science