On the spanning and routing ratio of Theta-Four

DOI10.1137/1.9781611975482.144zbMATH Open1432.68588arXiv1808.01298OpenAlexW2949684529MaRDI QIDQ5236331FDOQ5236331

Darryl Hill, Jean-Lou De Carufel, Michiel Smid, Prosenjit Bose

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: We present a routing algorithm for the directed $Thet{a}_4$-graph, here denoted as the $$-graph, that computes a path between any two vertices $s$ and $t$ having length at most $17$ times the Euclidean distance between $s$ and $t$. To compute this path, at each step, the algorithm only uses knowledge of the location of the current vertex, its (at most four) outgoing edges, the destination vertex, and one additional bit of information in order to determine the next edge to follow. This provides the first known online, local, competitive routing algorithm with constant routing ratio for the $Thet{a}_4$-graph, as well as improving the best known upper bound on the spanning ratio of these graphs from $237$ to $17$. We also show that without this additional bit of information, the routing ratio increases to $sqrt290approx17.03$.

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

Recommendations

• On the spanning ratio of theta-graphs
• Towards tight bounds on theta-graphs: more is not always better
• On the spanning and routing ratios of the directed \(\Theta_6\)-graph
• On the stretch factor of the theta-4 graph
• Expected complexity of routing in \(\Theta_6\) and half-\(\Theta_6\) graphs

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Cited In (8)

• Improved bounds on the spanning ratio of the theta-5-graph
• On the spanning and routing ratios of the directed \(\varTheta_6\)-graph
• Routing on heavy path WSPD spanners
• On the spanning and routing ratios of the directed \(\Theta_6\)-graph
• Spanning properties of Theta-Theta-6
• Truly Optimal Euclidean Spanners
• Generalized sweeping line spanners
• Emanation graph: a plane geometric spanner with Steiner points

This page was built for publication: On the spanning and routing ratio of Theta-Four

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