Small hop-diameter sparse spanners for doubling metrics
From MaRDI portal
Publication:5901493
DOI10.1007/s00454-008-9115-5zbMath1163.68039OpenAlexW3013884612MaRDI QIDQ5901493
Anupam Gupta, T.-H. Hubert Chan
Publication date: 24 March 2009
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00454-008-9115-5
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Demand-aware network designs of bounded degree ⋮ New Doubling Spanners: Better and Simpler ⋮ Vertex Fault-Tolerant Geometric Spanners for Weighted Points ⋮ Sparse fault-tolerant spanners for doubling metrics with bounded hop-diameter or degree ⋮ Fractal dimension and lower bounds for geometric problems ⋮ The Greedy Spanner Is Existentially Optimal ⋮ Unnamed Item ⋮ Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Computing on a free tree via complexity-preserving mappings
- On sparse spanners of weighted graphs
- Nearest neighbor queries in metric spaces
- Lectures on analysis on metric spaces
- A sparse graph almost as good as the complete graph on points in \(k\) dimensions
- Geometric Spanner Networks
- Finding nearest neighbors in growth-restricted metrics
- Bypassing the embedding
- Plongements lipschitziens dans ${\bbfR}\sp n$
- Graph spanners
- CONSTRUCTING MULTIDIMENSIONAL SPANNER GRAPHS
- Efficiency of a Good But Not Linear Set Union Algorithm
- A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
- NEW SPARSENESS RESULTS ON GRAPH SPANNERS
- Automata, Languages and Programming
- Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
- Compact routing on euclidian metrics
