The greedy spanner is existentially optimal
From MaRDI portal
Publication:4960447
DOI10.1137/18M1210678zbMATH Open1437.05221OpenAlexW3015517257MaRDI QIDQ4960447FDOQ4960447
Authors: Arnold Filtser, Shay Solomon 
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
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Cites Work
- Geometric Spanner Networks
- Title not available (Why is that?)
- Distributed Computing: A Locality-Sensitive Approach
- Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
- Computing almost shortest paths
- Lower bounds on the distortion of embedding finite metric spaces in graphs
- There are planar graphs almost as good as the complete graph
- An Optimal Synchronizer for the Hypercube
- On sparse spanners of weighted graphs
- Graph spanners
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Automata, Languages and Programming
- Title not available (Why is that?)
- Handbook of Approximation Algorithms and Metaheuristics
- Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
- Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
- A Fast Algorithm for Constructing Sparse Euclidean Spanners
- Light graphs with small routing cost
- NEW SPARSENESS RESULTS ON GRAPH SPANNERS
- Graph distances in the streaming model: the value of space
- The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension
- A trade-off between space and efficiency for routing tables
- Proximity-preserving labeling schemes
- Approximate distance oracles
- Computing the greedy spanner in near-quadratic time
- Distribution-sensitive construction of the greedy spanner
- Computing the greedy spanner in linear space
- An Optimal Dynamic Spanner for Doubling Metric Spaces
- Approximation algorithms via contraction decomposition
- Approximating the single-sink link-installation problem in network design
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- On dynamic shortest paths problems
- Light spanners
- Algorithms – ESA 2005
- Greedy spanners are optimal in doubling metrics
- Efficient algorithms for constructing very sparse spanners and emulators
- Deformable spanners and applications
- Near-optimal light spanners
- Title not available (Why is that?)
- Title not available (Why is that?)
- Optimal Euclidean Spanners
- Fast constructions of lightweight spanners for general graphs
- The greedy spanner is existentially optimal (extended abstract)
- Constructing Light Spanners Deterministically in Near-Linear Time
- Small hop-diameter sparse spanners for doubling metrics
- On notions of distortion and an almost minimum spanning tree with constant average distortion
- On hierarchical routing in doubling metrics
- Truly Optimal Euclidean Spanners
- From hierarchical partitions to hierarchical covers: optimal fault-tolerant spanners for doubling metrics
- Light spanners in bounded pathwidth graphs
- Fully dynamic geometric spanners
Cited In (8)
- Greedy spanners in Euclidean spaces admit sublinear separators
- Minimum weight Euclidean \((1+\varepsilon)\)-spanners
- The greedy spanner is existentially optimal (extended abstract)
- Truly Optimal Euclidean Spanners
- Local routing in sparse and lightweight geometric graphs
- Online Spanners in Metric Spaces
- Minimum weight Euclidean \((1+\varepsilon)\)-spanners
- Constructing light spanners deterministically in near-linear time
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)
