Computing the greedy spanner in near-quadratic time

DOI10.1007/S00453-009-9293-4MaRDI QIDQ1957650zbMATH OpenOpenAlexFDO

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

DilationDoubling dimensionGreedy algorithmSpannerStretch factor

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

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
• Distribution-sensitive construction of the greedy spanner

Cites work

• 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
• A note on two problems in connexion with graphs
• Algorithms – ESA 2005
• Approximating Euclidean distances by small degree graphs
• Bypassing the embedding
• Constructing sparse spanners for most graphs in higher dimensions
• 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
• Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
• Geometric Spanner Networks
• Graph spanners
• scientific article; zbMATH DE number 1424297 (Why is no real title available?)
• scientific article; zbMATH DE number 1424308 (Why is no real title available?)
• Introduction to algorithms
• NEW SPARSENESS RESULTS ON GRAPH SPANNERS
• On sparse spanners of weighted graphs

Cited in

(22)

• A spanner for the day after
• On path-greedy geometric spanners
• Computing the greedy spanner in linear space
• Space-Efficient and Output-Sensitive Implementations of Greedy Algorithms on Intervals
• Approximate greedy clustering and distance selection for graph metrics
• Computing the Greedy Spanner in Near-Quadratic Time
• The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• scientific article; zbMATH DE number 2038725 (Why is no real title available?)
• A framework for computing the greedy spanner
• The greedy spanner is existentially optimal
• A spanner for the day after
• Greedy spanners are optimal in doubling metrics
• Distribution-sensitive construction of the greedy spanner
• Vertex Fault-Tolerant Geometric Spanners for Weighted Points
• Vertex fault-tolerant spanners for weighted points in polygonal domains
• Engineering an algorithm for constructing low-stretch geometric graphs with near-greedy average degrees
• A unified framework of light spanners. I: Fast (yet optimal) constructions
• A quadtree, a Steiner spanner, and approximate nearest neighbours in hyperbolic space
• On the edge crossings of the greedy spanner
• Geometric spanners of bounded tree-width
• Computing the greedy spanner in linear space

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 Q1957650)