Distribution-sensitive construction of the greedy spanner

DOI10.1007/S00453-016-0160-9MaRDI QIDQ527422zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Sander P. A. Alewijnse, Quirijn W. Bouts, Alex P. ten Brink, Kevin Buchin

Publication date 11 May 2017

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00453-016-0160-9

zbMATH Keywords

computational geometryspannersgreedy spanneruniform points

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Distribution-sensitive construction of the greedy spanner
• A framework for computing the greedy spanner
• Improved deterministic distributed construction of spanners
• Distributed spanner approximation
• Distributed Spanner Approximation
• Computing the Greedy Spanner in Near-Quadratic Time
• Computing the greedy spanner in near-quadratic time
• Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
• Fast deterministic distributed algorithms for sparse spanners

Cites work

• scientific article; zbMATH DE number 4070353 (Why is no real title available?)
• scientific article; zbMATH DE number 732977 (Why is no real title available?)
• scientific article; zbMATH DE number 964350 (Why is no real title available?)
• A framework for computing the greedy spanner
• Approximating the Stretch Factor of Euclidean Graphs
• Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D
• Computing the greedy spanner in linear space
• Computing the greedy spanner in near-quadratic time
• Constructing Delaunay Triangulations along Space-Filling Curves
• Fast randomized point location without preprocessing in two- and three-dimensional Delaunay triangulations
• Geometric Spanner Networks
• Graph spanners
• Minimum dilation stars
• On the Spanning Ratio of Gabriel Graphs and beta-Skeletons
• On the expected maximum degree of Gabriel and Yao graphs
• Probability theory of classical Euclidean optimization problems
• Region-fault tolerant geometric spanners
• Some dynamic computational geometry problems
• Testing Euclidean Spanners
• The expected size of some graphs in computational geometry
• There are planar graphs almost as good as the complete graph

Cited in

(9)

• Distribution-sensitive construction of the greedy spanner
• A simple and efficient method for accelerating construction of the gap-greedy spanner
• Computing the greedy spanner in linear space
• A framework for computing the greedy spanner
• Computing the greedy spanner in linear space
• The emergence of sparse spanners and greedy well-separated pair decomposition
• \(\delta\)-greedy \(t\)-spanner
• The greedy spanner is existentially optimal
• Visualization of geometric spanner algorithms

This page was built for publication: Distribution-sensitive construction of the greedy spanner

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