New Doubling Spanners: Better and Simpler
From MaRDI portal
Publication:2954370
DOI10.1137/130930984zbMath1353.05043OpenAlexW2019731444MaRDI QIDQ2954370
Shay Solomon, Li Ning, T.-H. Hubert Chan, Mingfei Li
Publication date: 13 January 2017
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/10722/215509
Related Items
On Locality-Sensitive Orderings and Their Applications ⋮ Pattern matching in doubling spaces ⋮ Near isometric terminal embeddings for doubling metrics ⋮ Reliable Spanners for Metric Spaces ⋮ Vertex Fault-Tolerant Geometric Spanners for Weighted Points ⋮ Sometimes Reliable Spanners of Almost Linear Size. ⋮ Light Euclidean Spanners with Steiner Points ⋮ On Locality-Sensitive Orderings and Their Applications ⋮ Graph spanners: a tutorial review ⋮ Local routing in a tree metric \(1\)-spanner ⋮ Near Isometric Terminal Embeddings for Doubling Metrics
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Low-light trees, and tight lower bounds for Euclidean spanners
- Nearest neighbor queries in metric spaces
- Fault-tolerant geometric spanners
- Sparse Fault-Tolerant Spanners for Doubling Metrics with Bounded Hop-Diameter or Degree
- Distribution-Sensitive Construction of the Greedy Spanner
- Searching dynamic point sets in spaces with bounded doubling dimension
- Balancing Degree, Diameter, and Weight in Euclidean Spanners
- Geometric Spanner Networks
- An Optimal Dynamic Spanner for Doubling Metric Spaces
- Plongements lipschitziens dans ${\bbfR}\sp n$
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- From hierarchical partitions to hierarchical covers
- Deformable spanners and applications
- Fast construction of nets in low dimensional metrics, and their applications
- Optimal euclidean spanners
- Fully dynamic geometric spanners
- Small hop-diameter sparse spanners for doubling metrics
- Narrow-Shallow-Low-Light Trees with and without Steiner Points