Computing the greedy spanner in near-quadratic time
From MaRDI portal
Publication:1957650
DOI10.1007/s00453-009-9293-4zbMath1202.68469OpenAlexW3021716813MaRDI QIDQ1957650
Prosenjit Bose, Mohammad Farshi, Anil Maheshwari, Paz Carmi, Michiel H. M. Smid
Publication date: 27 September 2010
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-009-9293-4
Related Items (9)
On path-greedy geometric spanners ⋮ Computing the greedy spanner in linear space ⋮ Vertex Fault-Tolerant Geometric Spanners for Weighted Points ⋮ A spanner for the day after ⋮ Distribution-sensitive construction of the greedy spanner ⋮ Unnamed Item ⋮ Vertex fault-tolerant spanners for weighted points in polygonal domains ⋮ The Greedy Spanner Is Existentially Optimal ⋮ The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on two problems in connexion with graphs
- On sparse spanners of weighted graphs
- Approximating Euclidean distances by small degree graphs
- Constructing sparse spanners for most graphs in higher dimensions
- Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
- Geometric Spanner Networks
- Bypassing the embedding
- Graph spanners
- A Fast Algorithm for Constructing Sparse Euclidean Spanners
- A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
- Distributed Computing: A Locality-Sensitive Approach
- NEW SPARSENESS RESULTS ON GRAPH SPANNERS
- Experimental Study of Geometric t-Spanners: A Running Time Comparison
- Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
- Algorithms – ESA 2005
This page was built for publication: Computing the greedy spanner in near-quadratic time
