On the spanning and routing ratio of theta-four
We present a routing algorithm for the Θ4-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 Θ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 290 ≈ 17.03.
|Conference||30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019|
Bose, P, De Carufel, J.-L. (Jean-Lou), Hill, D. (Darryl), & Smid, M. (2019). On the spanning and routing ratio of theta-four. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 2361–2370).