| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
Expected Complexity of Routing in $\Theta_6$ and Half-$\Theta_6$ Graphs
Abstract : We study online routing algorithms on the $Θ 6$-graph and the half-$Θ 6$-graph (which is equivalent to a variant of the Delaunay triangulation). Given a source vertex s and a target vertex t in the $Θ 6$-graph (resp. half-Θ 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 $Θ 6$-graph and half-$Θ 6$-graph defined on a Poisson point process.
Cited literature [12 references]
https://hal.inria.fr/hal-02479502
Contributor : Olivier Devillers <>
Submitted on : Friday, February 14, 2020 - 3:18:43 PM
Last modification on : Tuesday, January 5, 2021 - 3:59:46 PM
Long-term archiving on: : Friday, May 15, 2020 - 4:15:17 PM
Contributor : Olivier Devillers <>
Submitted on : Friday, February 14, 2020 - 3:18:43 PM
Last modification on : Tuesday, January 5, 2021 - 3:59:46 PM
Long-term archiving on: : Friday, May 15, 2020 - 4:15:17 PM
Files
EuroCG-1.pdf
Files produced by the author(s)