.png){kind=icon}
.png){kind=icon}
Return
Distributed algorithm for the maximal 2-packing in geometric outerplanar graphs
.png){kind=icon}
PRE
AI
DOI：10.1016/j.jpdc.2013.12.002.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In this paper, we present a deterministic distributed algorithm that computes the maximal 2-packing set in a geometric outerplanar graph. In a geometric outerplanar graph, all the vertices have location coordinates in the plane and lie on the boundary of the graph. Our algorithm consists of three phases. First, it elects a vertex as the leader. Second, it explores the graph to determine relevant information about the structure of the input graph. Third, with this information, it computes a maximal 2-packing set. When the input graph is a ring, the algorithm computes a maximum 2-packing set. The execution time of this algorithm is O(n) steps and it uses O(n log n) messages. This algorithm does not require knowledge of the size of the input graph. To the best of our knowledge, this is the first deterministic distributed algorithm that solves such a problem for a geometric outerplanar graph in a linear number of steps. (C) 2013 Elsevier Inc. All rights reserved.
Keywords:
Distributed algorithm
Geometric graph
Outerplanar graph
Ear decomposition
2-packing set
Journal
IF:
4
Papers:
3.8K
Citations:
4.8K