Paper Info
Title
Distributed Local Approximation Of The Minimum K-Tuple Dominating Set In Planar Graphs
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 subset of 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 - is an element of)-approximation of the 2MDS problem. In addition, we show a lower bound of (4 - is an element of) 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.
Year
DOI
Venue
2014
10.1007/978-3-319-14472-6_4
PRINCIPLES OF DISTRIBUTED SYSTEMS, OPODIS 2014
Field
DocType
Volume
Integer,Combinatorics,Dominating set,Mathematical optimization,Vertex (geometry),Tuple,Upper and lower bounds,Computer science,Vertex cover,Local algorithm,Planar graph,Distributed computing
Conference
8878
ISSN
Citations 
PageRank 
0302-9743
1
0.36
References 
Authors
9
5
Name
Order
Citations
PageRank
Andrzej Czygrinow122725.81
Michal Hanćkowiak2816.66
Edyta Szymanska3465.53
Wojciech Wawrzyniak4978.23
Marcin Witkowski584.79