Truly Optimal Euclidean Spanners

DOI10.1137/20M1317906MaRDI QIDQ5071083zbMATH OpenOpenAlexWikidataFDO

Authors Hung Le, Shay Solomon

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

zbMATH Keywords

Euclidean spannerslight spannersspherical codesSteiner spanners

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Nonnumerical algorithms (68W05) Analysis of algorithms (68W40)

Cites work

• \(\pi /2\)-angle Xao graphs are spanners
• Almost All Even Yao-Yao Graphs Are Spanners
• An infinite class of Sparse-Yao spanners
• An Optimal Dynamic Spanner for Doubling Metric Spaces
• Approximate distance oracles for geometric spanners
• Classes of graphs which approximate the complete Euclidean graph
• Covering a ball with smaller equal balls in R^n
• Deformable spanners and applications
• Efficient construction of a bounded-degree spanner with low weight
• Efficient Regression in Metric Spaces via Approximate Lipschitz Extension
• Euclidean Steiner shallow-light trees
• Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
• From hierarchical partitions to hierarchical covers: optimal fault-tolerant spanners for doubling metrics
• Geometric Spanner Networks
• Greedy spanners are optimal in doubling metrics
• scientific article; zbMATH DE number 4070353 (Why is no real title available?)
• scientific article; zbMATH DE number 1263225 (Why is no real title available?)
• scientific article; zbMATH DE number 1979513 (Why is no real title available?)
• scientific article; zbMATH DE number 1532274 (Why is no real title available?)
• scientific article; zbMATH DE number 1775442 (Why is no real title available?)
• scientific article; zbMATH DE number 2119744 (Why is no real title available?)
• scientific article; zbMATH DE number 910877 (Why is no real title available?)
• Low-light trees, and tight lower bounds for Euclidean spanners
• Lower bound for sparse Euclidean spanners
• Lower bounds on the distortion of embedding finite metric spaces in graphs
• Near-optimal light spanners
• New and improved spanning ratios for Yao graphs
• NEW SPARSENESS RESULTS ON GRAPH SPANNERS
• Odd Yao-Yao graphs are not spanners
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• On hierarchical routing in doubling metrics
• On sparse spanners of weighted graphs
• On the spanning and routing ratio of Theta-Four
• Optimal Euclidean Spanners
• Small hop-diameter sparse spanners for doubling metrics
• Sparse communication networks and efficient routing in the plane (extended abstract)
• STACS 2005
• Steiner Minimal Trees
• Steiner Shallow-Light Trees are Exponentially Lighter than Spanning Ones
• The greedy spanner is existentially optimal
• The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension
• There are planar graphs almost as good as the complete graph
• Upper bounds on the spanning ratio of constrained theta-graphs

Cited in

(8)

• Light spanners for high dimensional norms via stochastic decompositions
• The greedy spanner is existentially optimal
• Euclidean Steiner spanners: light and sparse
• Minimum weight Euclidean (1+)-spanners
• Local routing algorithms on Euclidean spanners with small diameter
• Vertex Fault-Tolerant Geometric Spanners for Weighted Points
• Minimum weight Euclidean \((1+\varepsilon)\)-spanners
• A unified framework for light spanners

This page was built for publication: Truly Optimal Euclidean Spanners

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5071083)