The Greedy Spanner Is Existentially Optimal
From MaRDI portal
Publication:4960447
DOI10.1137/18M1210678zbMath1437.05221OpenAlexW3015517257MaRDI QIDQ4960447
Publication date: 16 April 2020
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/18m1210678
Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Local routing in sparse and lightweight geometric graphs, Truly Optimal Euclidean Spanners, Minimum weight Euclidean \((1+\varepsilon)\)-spanners, Minimum weight Euclidean \((1+\varepsilon)\)-spanners, Online Spanners in Metric Spaces, Constructing light spanners deterministically in near-linear time
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Distribution-sensitive construction of the greedy spanner
- On dynamic shortest paths problems
- Computing the greedy spanner in linear space
- On sparse spanners of weighted graphs
- Lower bounds on the distortion of embedding finite metric spaces in graphs
- There are planar graphs almost as good as the complete graph
- Approximation algorithms via contraction decomposition
- Computing the greedy spanner in near-quadratic time
- On notions of distortion and an almost minimum spanning tree with constant average distortion
- Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
- Approximating the Single-Sink Link-Installation Problem in Network Design
- Light Spanners in Bounded Pathwidth Graphs
- Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
- Optimal Euclidean Spanners
- Handbook of Approximation Algorithms and Metaheuristics
- Geometric Spanner Networks
- An Optimal Dynamic Spanner for Doubling Metric Spaces
- The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension
- Graph spanners
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- A Fast Algorithm for Constructing Sparse Euclidean Spanners
- Distributed Computing: A Locality-Sensitive Approach
- Light graphs with small routing cost
- Near-Optimal Light Spanners
- Efficient Algorithms for Constructing Very Sparse Spanners and Emulators
- NEW SPARSENESS RESULTS ON GRAPH SPANNERS
- A trade-off between space and efficiency for routing tables
- An Optimal Synchronizer for the Hypercube
- Proximity-preserving labeling schemes
- Fast Constructions of Lightweight Spanners for General Graphs
- On Hierarchical Routing in Doubling Metrics
- Truly Optimal Euclidean Spanners
- Constructing Light Spanners Deterministically in Near-Linear Time
- Approximate distance oracles
- Greedy spanners are optimal in doubling metrics
- From hierarchical partitions to hierarchical covers
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- Deformable spanners and applications
- The Greedy Spanner is Existentially Optimal
- Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
- Algorithms – ESA 2005
- Light Spanners
- Automata, Languages and Programming
- Computing almost shortest paths
- Small hop-diameter sparse spanners for doubling metrics
- Fully dynamic geometric spanners
