Competitive Routing on a Bounded-Degree Plane Spanner

Prosenjit Bose, Rolf Fagerberg, André van Renssen, Sander Verdonschot

Publikation: Kapitel i bog/rapport/konference-proceedingKapitel i bogForskningpeer review

Abstrakt

We show that it is possible to route locally and com-petitively on two bounded-degree plane 6-spanners, one with maximum degree 12 and the other with maximum degree 9. Both spanners are subgraphs of the empty equilateral triangle Delaunay triangulation. First, in a weak routing model where the only information stored at each vertex is its neighbourhood, we show how to find a path between any two vertices of a 6-spanner of max-imum degree 12, such that the path has length at most 95/ √ 3 times the straight-line distance between the ver-tices. In a slightly stronger model, where in addition to the neighbourhood of each vertex, we store O(1) addi-tional information, we show how to find a path that has length at most 15/ √ 3 times the Euclidean distance both in a 6-spanner of maximum degree 12 and a 6-spanner of maximum degree 9.
OriginalsprogEngelsk
TitelProceedings of the 24th Canadian Conference on Computational Geometry
Publikationsdato2012
Sider285-290
StatusUdgivet - 2012
BegivenhedThe 24th Canadian Conference on Computational Geometry - Charlottetown, Canada
Varighed: 8. aug. 201210. aug. 2012
Konferencens nummer: 24

Konference

KonferenceThe 24th Canadian Conference on Computational Geometry
Nummer24
Land/OmrådeCanada
ByCharlottetown
Periode08/08/201210/08/2012

Fingeraftryk

Dyk ned i forskningsemnerne om 'Competitive Routing on a Bounded-Degree Plane Spanner'. Sammen danner de et unikt fingeraftryk.

Citationsformater