Paper Info
Title
Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs.
Abstract
In this paper we consider the 2-dominating set problem (2MDS). We look for a smallest subset of vertices D⊆V with the property that every vertex in V∖D is adjacent to at least 2 vertices of D. We are interested in the distributed complexity of this problem in the local model, where the nodes have no identifiers but there is a port ordering available. We propose a distributed local (constant time) algorithm yielding a 6-approximation in the class of planar graphs. Earlier result shows that in this case, for any ϵ>0, there is no deterministic distributed local/constant-round algorithm providing a (5−ϵ)-approximation of the 2MDS.
Year
DOI
Venue
2017
10.1016/j.tcs.2016.12.001
Theoretical Computer Science
Keywords
Field
DocType
Distributed graph algorithms
Discrete mathematics,Approximation algorithm,Dominating set,Combinatorics,Vertex (geometry),Identifier,Independent set,Planar graph,Mathematics
Journal
Volume
ISSN
Citations 
662
0304-3975
0
PageRank 
References 
Authors
0.34
13
5
Name
Order
Citations
PageRank
Andrzej Czygrinow122725.81
Michal Hanćkowiak21016.56
Edyta Szymańska3445.04
Wojciech Wawrzyniak4978.23
Marcin Witkowski584.79