Linear time single-source shortest path algorithms in Euclidean graph classes
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _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 |