Greedy spanners are optimal in doubling metrics
From MaRDI portal
Publication:5236332
DOI10.1137/1.9781611975482.145zbMath1432.68340arXiv1712.05007OpenAlexW2774521735MaRDI QIDQ5236332
Hung Le, Glencora Borradaile, Christian Wulff-Nilsen
Publication date: 15 October 2019
Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1712.05007
Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items (14)
Euclidean Steiner Spanners: Light and Sparse ⋮ Pattern matching in doubling spaces ⋮ Local routing in sparse and lightweight geometric graphs ⋮ Truly Optimal Euclidean Spanners ⋮ Minimum weight Euclidean \((1+\varepsilon)\)-spanners ⋮ Minimum weight Euclidean \((1+\varepsilon)\)-spanners ⋮ Unnamed Item ⋮ Online Spanners in Metric Spaces ⋮ Unnamed Item ⋮ Light Euclidean Spanners with Steiner Points ⋮ Bounded-degree light approximate shortest-path trees in doubling metrics ⋮ Graph spanners: a tutorial review ⋮ The Greedy Spanner Is Existentially Optimal ⋮ Light spanners for high dimensional norms via stochastic decompositions
This page was built for publication: Greedy spanners are optimal in doubling metrics
