Computing the Greedy Spanner in Near-Quadratic Time

DOI10.1007/978-3-540-69903-3_35zbMATH Open1155.68548OpenAlexW1969798922MaRDI QIDQ3512475FDOQ3512475

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

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

Mathematics Subject Classification ID

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

Cites Work

• Geometric Spanner Networks
• Distributed Computing: A Locality-Sensitive Approach
• Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
• On sparse spanners of weighted graphs
• Graph spanners
• Classes of graphs which approximate the complete Euclidean graph
• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
• A Fast Algorithm for Constructing Sparse Euclidean Spanners
• Experimental Study of Geometric t-Spanners: A Running Time Comparison
• Algorithms – ESA 2005

Cited In (8)

• \( \delta \)-greedy \(t\)-spanner
• Minimum weight Euclidean \(t\)-spanner is NP-hard
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Computing the greedy spanner in near-quadratic time
• Title not available (Why is that?)
• Space-Efficient and Output-Sensitive Implementations of Greedy Algorithms on Intervals
• Greedy spanners are optimal in doubling metrics
• Distribution-sensitive construction of the greedy spanner

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)