Light Euclidean Spanners with Steiner Points
From MaRDI portal
(Redirected from Publication:5874539)
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+)-spanners
Cites work
- \(\delta\)-greedy \(t\)-spanner
- A PTAS for subset TSP in minor-free graphs
- A subset spanner for Planar graphs, with application to subset TSP
- A treehouse with custom windows: minimum distortion embeddings into bounded treewidth graphs
- Algorithms – ESA 2005
- Algorithms and Computation
- Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces
- Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\)
- Approximate distance oracles for geometric spanners
- Better distance preservers and additive spanners
- Classes of graphs which approximate the complete Euclidean graph
- Clustering motion
- Constructing Light Spanners Deterministically in Near-Linear Time
- Constructing sparse spanners for most graphs in higher dimensions
- Deformable spanners and applications
- Dense point sets have sparse Delaunay triangulations or ``\dots but not too nasty
- Effectiveness of local search for geometric optimization
- Efficient construction of a bounded-degree spanner with low weight
- Euclidean Steiner shallow-light trees
- Experimental Study of Geometric t-Spanners: A Running Time Comparison
- Faster algorithms for the geometric transportation problem
- Geometric approximation algorithms
- Geometric Spanner Networks
- Greedy spanners are optimal in doubling metrics
- How fast is the \(k\)-means method?
- scientific article; zbMATH DE number 4070353 (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?)
- scientific article; zbMATH DE number 3193293 (Why is no real title available?)
- Light spanners
- Light spanners for high dimensional norms via stochastic decompositions
- Low-distortion embeddings of general metrics into the line
- Narrow-Shallow-Low-Light Trees with and without Steiner Points
- Near-optimal light spanners
- Near-optimal light spanners
- Net and prune: a linear time algorithm for Euclidean distance problems
- New constructions of SSPDs and their applications
- New Doubling Spanners: Better and Simpler
- On a Family of Strong Geometric Spanners That Admit Local Routing Strategies
- On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
- On hierarchical routing in doubling metrics
- On sparse spanners of weighted graphs
- Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
- Sparse communication networks and efficient routing in the plane (extended abstract)
- STACS 2005
- Steiner shallow-light trees are exponentially lighter than spanning ones
- The minimum Manhattan network problem: Approximations and exact solutions
- There are planar graphs almost as good as the complete graph
- Viewing the rings of a tree: minimum distortion embeddings into trees
- Well-separated pair decomposition in linear time?
Cited in
(10)- Euclidean Steiner spanners: light and sparse
- Minimum weight Euclidean (1+)-spanners
- Online Spanners in Metric Spaces
- Minimum weight Euclidean \((1+\varepsilon)\)-spanners
- A unified framework for light spanners
- A gap-ETH-tight approximation scheme for Euclidean TSP
- Online spanners in metric spaces
- Online Euclidean spanners
- On euclidean Steiner (1+)-spanners
- Light Euclidean Steiner spanners in the plane
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)
