Hop-spanners for geometric intersection graphs
A $t$-spanner of a graph $G=(V,E)$ is a subgraph $H=(V,E')$ that contains a $uv$-path of length at most $t$ for every $uv \in E$. It is known that every $n$-vertex graph admits a $(2k-1)$-spanner with $O(n^{1+1/k})$ edges for $k \geq 1$. This bound is the best possible for $1 \leq k \leq 9$ and is...
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Artigo |
| Lenguaje: | Inglês |
| Publicado: |
Carleton University
2023-12-01
|
| Colección: | Journal of Computational Geometry |
| Acceso en línea: | https://jocg.org/index.php/jocg/article/view/4475 |
| Etiquetas: |
Sin Etiquetas, Sea el primero en etiquetar este registro!
|