Linear time single-source shortest path algorithms in Euclidean graph classes
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912980217626624 |
|---|---|
| author | Gudmundsson, Joachim Sha, Yuan Wong, Sampson |
| author_facet | Gudmundsson, Joachim Sha, Yuan Wong, Sampson |
| contents | In the celebrated paper of Henzinger, Klein, Rao and Subramanian (1997), it was shown that planar graphs admit a linear time single-source shortest path algorithm. Their algorithm unfortunately does not extend to Euclidean graph classes. We give criteria and prove that any Euclidean graph class satisfying the criteria admits a linear time single-source shortest path algorithm. As a main ingredient, we show that the contracted graphs of these Euclidean graph classes admit sublinear separators. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_22948 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Linear time single-source shortest path algorithms in Euclidean graph classes Gudmundsson, Joachim Sha, Yuan Wong, Sampson Computational Geometry In the celebrated paper of Henzinger, Klein, Rao and Subramanian (1997), it was shown that planar graphs admit a linear time single-source shortest path algorithm. Their algorithm unfortunately does not extend to Euclidean graph classes. We give criteria and prove that any Euclidean graph class satisfying the criteria admits a linear time single-source shortest path algorithm. As a main ingredient, we show that the contracted graphs of these Euclidean graph classes admit sublinear separators. |
| title | Linear time single-source shortest path algorithms in Euclidean graph classes |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2603.22948 |