Paper Info
Title
A local approximation algorithm for minimum dominating set problem in anonymous planar networks
Abstract
A dominating set in a graph is a subset of vertices such that every vertex in belongs to or has at least one neighbour in . In this paper we deal with the problem of finding an approximation of the dominating set of minimum size, i.e., the approximation of the minimum dominating set problem (MDS) in a distributed setting. A distributed algorithm that runs in a constant number of rounds, independent of the size of the network, is called . In research on distributed local algorithms it is commonly assumed that each vertex has an unique identifier. However, as was shown by Göös et al., for certain classes of graphs (for example, lift-closed bounded degree graphs) identifiers are unnecessary and only a port numbering is needed. We confirm that the same remains true for the MDS up to a constant factor in the class of planar graphs. Namely, we present a local deterministic 694-approximation algorithm for the MDS in planar graphs in a model with a port numbering only. Moreover, our algorithm uses only short messages, i.e., in each round each node can send only a -bit message to each of its neighbours.
Year
DOI
Venue
2015
10.1007/s00446-015-0247-6
Distributed Computing
Keywords
Field
DocType
Approximation,Local algorithm,Dominating set,Planar graph
Numbering,Approximation algorithm,Dominating set,Mathematical optimization,Combinatorics,Petroleum engineering,Independent set,Local algorithm,Engineering,Planar graph,Bidimensionality,Maximal independent set
Journal
Volume
Issue
ISSN
28
5
0178-2770
Citations 
PageRank 
References 
2
0.39
14
Authors
1
Name
Order
Citations
PageRank
Wojciech Wawrzyniak1978.23