Light Euclidean Spanners with Steiner Points
From MaRDI portal
Publication:5874539
DOI10.4230/LIPICS.ESA.2020.67OpenAlexW3082819694MaRDI QIDQ5874539FDOQ5874539
Authors: Hung Le, Shay Solomon 
Publication date: 7 February 2023
Full work available at URL: https://arxiv.org/abs/2007.11636
Recommendations
- Euclidean Steiner spanners: light and sparse
- Euclidean Steiner shallow-light trees
- Euclidean Steiner shallow-light trees
- On spanners and lightweight spanners of geometric graphs
- Approximate Euclidean Steiner trees
- Near-linear-time deterministic plane Steiner spanners for well-spaced point sets
- Optimal Euclidean Spanners
- Light spanners in bounded pathwidth graphs
- Minimum weight Euclidean \((1+\varepsilon)\)-spanners
Cites Work
- Geometric Spanner Networks
- There are planar graphs almost as good as the complete graph
- On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
- On sparse spanners of weighted graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Clustering motion
- Deformable spanners and applications
- Geometric approximation algorithms
- Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
- Classes of graphs which approximate the complete Euclidean graph
- Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Dense point sets have sparse Delaunay triangulations or ``\dots but not too nasty
- Low-distortion embeddings of general metrics into the line
- How fast is the \(k\)-means method?
- A subset spanner for Planar graphs, with application to subset TSP
- Net and prune: a linear time algorithm for Euclidean distance problems
- The minimum Manhattan network problem: Approximations and exact solutions
- On a Family of Strong Geometric Spanners That Admit Local Routing Strategies
- Efficient construction of a bounded-degree spanner with low weight
- New constructions of SSPDs and their applications
- Well-separated pair decomposition in linear time?
- Faster algorithms for the geometric transportation problem
- Light spanners
- Constructing sparse spanners for most graphs in higher dimensions
- Experimental Study of Geometric t-Spanners: A Running Time Comparison
- Algorithms – ESA 2005
- New Doubling Spanners: Better and Simpler
- Greedy spanners are optimal in doubling metrics
- Title not available (Why is that?)
- Title not available (Why is that?)
- STACS 2005
- Title not available (Why is that?)
- Sparse communication networks and efficient routing in the plane (extended abstract)
- Better distance preservers and additive spanners
- Near-optimal light spanners
- Near-optimal light spanners
- Algorithms and Computation
- Effectiveness of local search for geometric optimization
- Approximate distance oracles for geometric spanners
- Constructing Light Spanners Deterministically in Near-Linear Time
- On hierarchical routing in doubling metrics
- Title not available (Why is that?)
- Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces
- Narrow-Shallow-Low-Light Trees with and without Steiner Points
- \(\delta\)-greedy \(t\)-spanner
- Euclidean Steiner shallow-light trees
- A treehouse with custom windows: minimum distortion embeddings into bounded treewidth graphs
- Steiner shallow-light trees are exponentially lighter than spanning ones
- A PTAS for subset TSP in minor-free graphs
- Viewing the rings of a tree: minimum distortion embeddings into trees
Cited In (5)
This page was built for publication: Light Euclidean Spanners with Steiner Points
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5874539)
