An optimal greedy routing algorithm for triangulated polygons (Q1947976): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 17:06, 1 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An optimal greedy routing algorithm for triangulated polygons |
scientific article |
Statements
An optimal greedy routing algorithm for triangulated polygons (English)
0 references
29 April 2013
0 references
In a greedy routing on a graph, each node forward messages to a neighbor that is closer to the destination. There are configurations of the graph where message delivery cannot always be guaranteed. A solution to this problems was to use a kind of virtual coordinates for the nodes instead of using real geometric coordinates. However, once the delivery guarantee problem was solved, another problem arose, that of achieving a simple representation of the virtual coordinates of each vertex. In the recent paper [\textit{H. Zhang} and \textit{S. Govindaiah}, Lect. Notes Comput. Sci. 6681, 58--69 (2011; Zbl 1329.90155)] the authors observed that in order for greedy routing to work, there is no need to embed the graph in a metric space. Instead, they used greedy embedding of graphs into semi-metric spaces. According with this approach, the main result in the paper under review is to show that any triangulated polygon with more than 3 vertices admits an optimal greedy routing algorithm, via a greedy embedding into an appropriate semi-metric space. The embedding is constructible in linear time and every node is representable in \(O(\text{deg}(\nu)\log(n))\) bits, being \(\text{deg}(\nu)\) the degree of the node \(\nu\).
0 references
greedy routing
0 references
stretch factor
0 references