Euclidean Steiner Spanners: Light and Sparse

DOI10.1137/22M1502707zbMath1498.05258arXiv2206.09648MaRDI QIDQ5043642

Sujoy Bhore, Csaba D. Tóth

Publication date: 6 October 2022

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

minimum weightsparsitygeometric spannerlightness\((1+\varepsilon)\)-spanner

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Combinatorial complexity of geometric structures (52C45)

Related Items (3)

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
• On plane geometric spanners: a survey and open problems
• Minimum weight convex Steiner partitions
• Constructing plane spanners of bounded degree and low weight
• Geometric spanners with applications in wireless networks
• Near-linear-time deterministic plane Steiner spanners for well-spaced point sets
• I/O-efficient algorithms for computing planar geometric spanners
• Light orthogonal networks with constant geometric dilation
• Classes of graphs which approximate the complete Euclidean graph
• On sparse spanners of weighted graphs
• Rectilinear decompositions with low stabbing number
• There are planar graphs almost as good as the complete graph
• Efficient construction of a bounded-degree spanner with low weight
• Competitive concurrent distributed queuing
• Euclidean Steiner shallow-light trees
• Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
• Geometric Spanner Networks
• Worst-Case Growth Rates of Some Classical Problems of Combinatorial Optimization
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• Planar spanners and approximate shortest path queries among obstacles in the plane
• A trade-off between space and efficiency for routing tables
• An Optimal Synchronizer for the Hypercube
• Approximate distance oracles for geometric spanners
• Truly Optimal Euclidean Spanners
• Greedy spanners are optimal in doubling metrics
• Efficient Regression in Metric Spaces via Approximate Lipschitz Extension
• Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones
• Light Euclidean Spanners with Steiner Points

This page was built for publication: Euclidean Steiner Spanners: Light and Sparse