Computing the Greedy Spanner in Near-Quadratic Time

DOI10.1007/978-3-540-69903-3_35MaRDI QIDQ3512475zbMATH OpenOpenAlexFDO

Authors Prosenjit Bose, Paz Carmi, Mohammad Farshi, Anil Maheshwari, Michiel 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)

Recommendations

• Computing the greedy spanner in near-quadratic time
• Computing the greedy spanner in linear space
• Computing the greedy spanner in linear space
• A framework for computing the greedy spanner
• Greedy spanners are optimal in doubling metrics

Cites work

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

Cited in

(10)

• Approximate greedy clustering and distance selection for graph metrics
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Computing the greedy spanner in near-quadratic time
• Greedy spanners are optimal in doubling metrics
• \( \delta \)-greedy \(t\)-spanner
• Minimum weight Euclidean \(t\)-spanner is NP-hard
• Greedy spanners in Euclidean spaces admit sublinear separators
• scientific article; zbMATH DE number 2038725 (Why is no real title available?)
• Distribution-sensitive construction of the greedy spanner
• Space-Efficient and Output-Sensitive Implementations of Greedy Algorithms on Intervals

This page was built for publication: Computing the Greedy Spanner in Near-Quadratic Time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3512475)