Light Euclidean Spanners with Steiner Points

DOI10.4230/LIPIcs.ESA.2020.67OpenAlexW3082819694MaRDI QIDQ5874539

Shay Solomon, Hung Le

Publication date: 7 February 2023

Full work available at URL: https://arxiv.org/abs/2007.11636

zbMATH Keywords

Euclidean spannerslight spannersSteiner spanners

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (4)

Euclidean Steiner Spanners: Light and Sparse ⋮ Minimum weight Euclidean \((1+\varepsilon)\)-spanners ⋮ Minimum weight Euclidean \((1+\varepsilon)\)-spanners ⋮ Online Spanners in Metric Spaces

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\)
• Well-separated pair decomposition in linear time?
• Classes of graphs which approximate the complete Euclidean graph
• On sparse spanners of weighted graphs
• Constructing sparse spanners for most graphs in higher dimensions
• Dense point sets have sparse Delaunay triangulations or ``\dots but not too nasty
• There are planar graphs almost as good as the complete graph
• Clustering motion
• Efficient construction of a bounded-degree spanner with low weight
• \(\delta\)-greedy \(t\)-spanner
• The minimum Manhattan network problem: Approximations and exact solutions
• Deformable spanners and applications
• A subset spanner for Planar graphs, with application to subset TSP
• Balancing Degree, Diameter, and Weight in Euclidean Spanners
• New Doubling Spanners: Better and Simpler
• Euclidean Steiner shallow-light trees
• Net and Prune
• Geometric Spanner Networks
• Low-distortion embeddings of general metrics into the line
• On a Family of Strong Geometric Spanners That Admit Local Routing Strategies
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
• Near-Optimal Light Spanners
• Better Distance Preservers and Additive Spanners
• Near-Optimal Light Spanners
• A Treehouse with Custom Windows: Minimum Distortion Embeddings into Bounded Treewidth Graphs
• On Hierarchical Routing in Doubling Metrics
• Approximate distance oracles for geometric spanners
• Constructing Light Spanners Deterministically in Near-Linear Time
• A PTAS for subset TSP in minor-free graphs
• Sparse communication networks and efficient routing in the plane (extended abstract)
• Greedy spanners are optimal in doubling metrics
• Viewing the Rings of a Tree: Minimum Distortion Embeddings into Trees
• New constructions of SSPDs and their applications
• Experimental Study of Geometric t-Spanners: A Running Time Comparison
• Algorithms – ESA 2005
• Light Spanners
• Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones
• STACS 2005
• Narrow-Shallow-Low-Light Trees with and without Steiner Points
• Algorithms and Computation

This page was built for publication: Light Euclidean Spanners with Steiner Points