Paper Info
Title
A local constant-factor approximation algorithm for MDS problem in anonymous network
Abstract
In research on distributed local algorithms it is commonly assumed that each vertex has a unique identifier in the entire graph. However, it turns out that in case of certain classes of graphs (for example not lift-closed bounded degree graphs) identifiers are unnecessary and only a port ordering is needed. One of the open issues was whether identifiers are essential in planar graphs. In this paper, we answer this question and we propose an algorithm which returns constant approximation of the MDS problem in CONGEST model. The algorithm doesn't use any additional information about the structure of the graph and the nodes don't have unique identifiers. We hope that this paper will be very helpful as a hint for further comparisons of the unique identifier model and the model with only a port numbering in other classes of graphs.
Year
Venue
Field
2013
CoRR
Discrete mathematics,Approximation algorithm,Numbering,Indifference graph,Combinatorics,Identifier,Theoretical computer science,Pathwidth,1-planar graph,Unique identifier,Mathematics,Planar graph
DocType
Volume
Citations 
Journal
abs/1303.2514
0
PageRank 
References 
Authors
0.34
10
1
Name
Order
Citations
PageRank
Wojciech Wawrzyniak1978.23