Truly Optimal Euclidean Spanners
From MaRDI portal
Publication:5071083
DOI10.1137/20M1317906OpenAlexW4221056862WikidataQ114074214 ScholiaQ114074214MaRDI QIDQ5071083
Publication date: 20 April 2022
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1904.12042
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items (7)
Euclidean Steiner Spanners: Light and Sparse ⋮ Minimum weight Euclidean \((1+\varepsilon)\)-spanners ⋮ Minimum weight Euclidean \((1+\varepsilon)\)-spanners ⋮ Local routing algorithms on Euclidean spanners with small diameter ⋮ Vertex Fault-Tolerant Geometric Spanners for Weighted Points ⋮ The Greedy Spanner Is Existentially Optimal ⋮ Light spanners for high dimensional norms via stochastic decompositions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Low-light trees, and tight lower bounds for Euclidean spanners
- Classes of graphs which approximate the complete Euclidean graph
- On sparse spanners of weighted graphs
- Lower bounds on the distortion of embedding finite metric spaces in graphs
- Covering a ball with smaller equal balls in \(\mathbb R^n\)
- There are planar graphs almost as good as the complete graph
- Efficient construction of a bounded-degree spanner with low weight
- Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
- Optimal Euclidean Spanners
- Geometric Spanner Networks
- An Optimal Dynamic Spanner for Doubling Metric Spaces
- The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension
- On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
- Near-Optimal Light Spanners
- Almost All Even Yao-Yao Graphs Are Spanners
- New and Improved Spanning Ratios for Yao Graphs
- Euclidean Steiner Shallow-Light Trees
- π/2-ANGLE YAO GRAPHS ARE SPANNERS
- NEW SPARSENESS RESULTS ON GRAPH SPANNERS
- The Greedy Spanner Is Existentially Optimal
- On Hierarchical Routing in Doubling Metrics
- Approximate distance oracles for geometric spanners
- Odd Yao-Yao Graphs are Not Spanners
- Sparse communication networks and efficient routing in the plane (extended abstract)
- On the Spanning and Routing Ratio of Theta-Four
- Greedy spanners are optimal in doubling metrics
- From hierarchical partitions to hierarchical covers
- Deformable spanners and applications
- Efficient Regression in Metric Spaces via Approximate Lipschitz Extension
- Upper Bounds on the Spanning Ratio of Constrained Theta-Graphs
- Steiner Shallow-Light Trees are Exponentially Lighter than Spanning Ones
- Steiner Minimal Trees
- STACS 2005
- An Infinite Class of Sparse-Yao Spanners
- Small hop-diameter sparse spanners for doubling metrics
This page was built for publication: Truly Optimal Euclidean Spanners
