Paper Info
Title
A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
Abstract
In recent years growing interest in local distributed algorithms has widely been observed. This results from their high resistance to errors and damage, as well as from their good performance, which is independent of the size of the network. A local deterministic distributed algorithm finding an approximation of a Minimum Dominating Set in planar graphs has been presented by Lenzen et al., and they proved that the algorithm returns a 130-approximation of the Minimum Dominating Set. In this article we will show that the algorithm is two times more effective than was previously assumed, and we prove that the algorithm by Lenzen et al. outputs a 52-approximation to a Minimum Dominating Set. Therefore the gap between the lower bound and the approximation ratio of the best yet local deterministic distributed algorithm is reduced by half.
Year
DOI
Venue
2014
10.1016/j.ipl.2013.11.008
Inf. Process. Lett.
Keywords
Field
DocType
algorithm return,approximation ratio,planar graph,good performance,local deterministic,local algorithm,minimum dominating set problem,minimum dominating set,strengthened analysis,recent year,high resistance,dominating set,distributed algorithm,approximation algorithms
Discrete mathematics,Approximation algorithm,Combinatorics,Dominating set,Upper and lower bounds,Distributed algorithm,Local algorithm,Mathematics,Minimum dominating set,Planar graph,Maximal independent set
Journal
Volume
Issue
ISSN
114
3
0020-0190
Citations 
PageRank 
References 
9
0.63
7
Authors
1
Name
Order
Citations
PageRank
Wojciech Wawrzyniak1978.23