Expected complexity of routing in _6 and half-_6 graphs

DOI10.20382/JOCG.V11I1A9MaRDI QIDQ5120153zbMATH OpenOpenAlexFDO

Authors Prosenjit Brose, Jean-Lou De Carufel, Olivier Devillers

Publication date 9 September 2020

Full work available at URL https://arxiv.org/abs/1910.14289

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Online algorithms; streaming algorithms (68W27)

Abstract: We study online routing algorithms on the $Theta$6-graph and the half-$Theta$6-graph (which is equivalent to a variant of the Delaunay triangulation). Given a source vertex s and a target vertex t in the $Theta$6-graph (resp. half-$Theta$6-graph), there exists a deterministic online routing algorithm that finds a path from s to t whose length is at most 2 st (resp. 2.89 st) which is optimal in the worst case [Bose et al., siam J. on Computing, 44(6)]. We propose alternative, slightly simpler routing algorithms that are optimal in the worst case and for which we provide an analysis of the average routing ratio for the $Theta$6-graph and half-$Theta$6-graph defined on a Poisson point process. For the $Theta$6-graph, our online routing algorithm has an expected routing ratio of 1.161 (when s and t random) and a maximum expected routing ratio of 1.22 (maximum for fixed s and t where all other points are random), much better than the worst-case routing ratio of 2. For the half-$Theta$6-graph, our memoryless online routing algorithm has an expected routing ratio of 1.43 and a maximum expected routing ratio of 1.58. Our online routing algorithm that uses a constant amount of additional memory has an expected routing ratio of 1.34 and a maximum expected routing ratio of 1.40. The additional memory is only used to remember the coordinates of the starting point of the route. Both of these algorithms have an expected routing ratio that is much better than their worst-case routing ratio of 2.89.

Recommendations

• Competitive routing in the half-\(\theta_6\)-graph
• On the spanning and routing ratios of the directed _6-graph
• On the spanning and routing ratio of Theta-Four
• Optimal local routing on Delaunay triangulations defined by empty equilateral triangles
• Online Routing in Triangulations

Cited in

(9)

• On the spanning and routing ratios of the directed _6-graph
• On the average number of edges in theta graphs
• On the spanning and routing ratio of Theta-Four
• Competitive routing in the half-\(\theta_6\)-graph
• On the spanning and routing ratio of the directed theta-four graph
• Local routing on ordered -graphs
• Local routing on ordered \(\Theta\)-graphs
• On the spanning and routing ratios of the directed _6-graph
• Routing on heavy-path WSPD-spanners

This page was built for publication: Expected complexity of routing in \(\Theta_6\) and half-\(\Theta_6\) graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5120153)