Local Routing on Ordered $Θ$-graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911013594464256 |
|---|---|
| author | van Renssen, André Sakaguchi, Shuei |
| author_facet | van Renssen, André Sakaguchi, Shuei |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_16021 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Local Routing on Ordered $Θ$-graphs van Renssen, André Sakaguchi, Shuei Computational Geometry Data Structures and Algorithms 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. |
| title | Local Routing on Ordered $Θ$-graphs |
| topic | Computational Geometry Data Structures and Algorithms |
| url | https://arxiv.org/abs/2506.16021 |