The greedy spanner is existentially optimal
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 1670877 (Why is no real title available?)
- scientific article; zbMATH DE number 5764857 (Why is no real title available?)
- scientific article; zbMATH DE number 2119747 (Why is no real title available?)
- scientific article; zbMATH DE number 3258067 (Why is no real title available?)
- A Fast Algorithm for Constructing Sparse Euclidean Spanners
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- A trade-off between space and efficiency for routing tables
- Algorithms – ESA 2005
- An Optimal Dynamic Spanner for Doubling Metric Spaces
- An Optimal Synchronizer for the Hypercube
- Approximate distance oracles
- Approximating the single-sink link-installation problem in network design
- Approximation algorithms via contraction decomposition
- Automata, Languages and Programming
- Computing almost shortest paths
- Computing the greedy spanner in linear space
- Computing the greedy spanner in near-quadratic time
- Constructing Light Spanners Deterministically in Near-Linear Time
- Deformable spanners and applications
- Distributed Computing: A Locality-Sensitive Approach
- Distribution-sensitive construction of the greedy spanner
- Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
- Efficient algorithms for constructing very sparse spanners and emulators
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
- Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
- Fast constructions of lightweight spanners for general graphs
- From hierarchical partitions to hierarchical covers: optimal fault-tolerant spanners for doubling metrics
- Fully dynamic geometric spanners
- Geometric Spanner Networks
- Graph distances in the streaming model: the value of space
- Graph spanners
- Greedy spanners are optimal in doubling metrics
- Handbook of Approximation Algorithms and Metaheuristics
- Light graphs with small routing cost
- Light spanners
- Light spanners in bounded pathwidth graphs
- Lower bounds on the distortion of embedding finite metric spaces in graphs
- NEW SPARSENESS RESULTS ON GRAPH SPANNERS
- Near-optimal light spanners
- On dynamic shortest paths problems
- On hierarchical routing in doubling metrics
- On notions of distortion and an almost minimum spanning tree with constant average distortion
- On sparse spanners of weighted graphs
- Optimal Euclidean Spanners
- Proximity-preserving labeling schemes
- Small hop-diameter sparse spanners for doubling metrics
- The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension
- The greedy spanner is existentially optimal (extended abstract)
- There are planar graphs almost as good as the complete graph
- Truly Optimal Euclidean Spanners
Cited in
(18)- Online spanners in metric spaces
- An alternate proof of near-optimal light spanners
- Greedy spanners in Euclidean spaces admit sublinear separators
- Lightweight near-additive spanners
- Minimum weight Euclidean (1+)-spanners
- The greedy spanner is existentially optimal (extended abstract)
- Truly Optimal Euclidean Spanners
- Local routing in sparse and lightweight geometric graphs
- Exploration of graphs with excluded minors
- Online Spanners in Metric Spaces
- Minimum weight Euclidean \((1+\varepsilon)\)-spanners
- Bicriteria approximation for minimum dilation graph augmentation
- A gap-ETH-tight approximation scheme for Euclidean TSP
- Engineering an algorithm for constructing low-stretch geometric graphs with near-greedy average degrees
- A unified framework of light spanners. I: Fast (yet optimal) constructions
- Light, reliable spanners
- Constructing light spanners deterministically in near-linear time
- Truly optimal Euclidean spanners
This page was built for publication: The greedy spanner is existentially optimal
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4960447)
