DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2025.52

Local Routing on Ordered Θ-Graphs

Authors: André van Renssen and Shuei Sakaguchi

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract

The problem of locally routing on geometric networks using limited memory is extensively studied in computational geometry. We consider one particular graph, the ordered Θ-graph, which is significantly harder to route on than the Θ-graph, for which a number of routing algorithms are known. Currently, no local routing algorithm is known for the ordered Θ-graph. We prove that, unfortunately, there does not exist a deterministic memoryless local routing algorithm that works on the ordered Θ-graph. This motivates us to consider allowing a small amount of memory, and we present a deterministic O(1)-memory local routing algorithm that successfully routes from the source to the destination on the ordered Θ-graph. We show that our local routing algorithm converges to the destination in O(n) hops, where n is the number of vertices. To the best of our knowledge, our algorithm is the first deterministic local routing algorithm that is guaranteed to reach the destination on the ordered Θ-graph.

Cite as

André van Renssen and Shuei Sakaguchi. Local Routing on Ordered Θ-Graphs. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 52:1-52:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{vanrenssen_et_al:LIPIcs.ISAAC.2025.52,
  author =	{van Renssen, Andr\'{e} and Sakaguchi, Shuei},
  title =	{{Local Routing on Ordered \Theta-Graphs}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{52:1--52:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.52},
  URN =		{urn:nbn:de:0030-drops-249607},
  doi =		{10.4230/LIPIcs.ISAAC.2025.52},
  annote =	{Keywords: Ordered \Theta-graph, Local routing, Computational geometry}
}

Search Results

Documents authored by Sakaguchi, Shuei

Local Routing on Ordered Θ-Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message