Computing the greedy spanner in near-quadratic time

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

zbMATH Keywords

Greedy algorithmDilationStretch factorSpannerDoubling dimension

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

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