Computing the Greedy Spanner in Near-Quadratic Time

DOI10.1007/978-3-540-69903-3_35zbMath1155.68548OpenAlexW1969798922MaRDI QIDQ3512475

Prosenjit Bose, Paz Carmi, Anil Maheshwari, Mohammad Farshi, Michiel H. M. Smid

Publication date: 15 July 2008

Published in: Algorithm Theory – SWAT 2008 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-69903-3_35

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (2)

\( \delta \)-greedy \(t\)-spanner ⋮ Minimum weight Euclidean \(t\)-spanner is NP-hard

Cites Work

• Classes of graphs which approximate the complete Euclidean graph
• On sparse spanners of weighted graphs
• Geometric Spanner Networks
• 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
• 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