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...
Đã lưu trong:
| Những tác giả chính: | , |
|---|---|
| Định dạng: | Artigo |
| Ngôn ngữ: | Inglês |
| Được phát hành: |
Carleton University
2023-12-01
|
| Loạt: | Journal of Computational Geometry |
| Truy cập trực tuyến: | https://jocg.org/index.php/jocg/article/view/4475 |
| Các nhãn: |
Không có thẻ, Là người đầu tiên thẻ bản ghi này!
|