Computing the greedy spanner in linear space

DOI10.1007/s00453-015-0001-2zbMath1325.68245OpenAlexW2126497992WikidataQ59427635 ScholiaQ59427635MaRDI QIDQ893321

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

Publication date: 19 November 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-015-0001-2

zbMATH Keywords

greedy algorithmdilationcomputational geometrygeometric spannerstretch factor

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (3)

\( \delta \)-greedy \(t\)-spanner ⋮ Distribution-sensitive construction of the greedy spanner ⋮ The Greedy Spanner Is Existentially Optimal

Cites Work

• Unnamed Item
• Unnamed Item
• There are planar graphs almost as good as the complete graph
• Computing the greedy spanner in near-quadratic time
• Distribution-Sensitive Construction of the Greedy Spanner
• Geometric Spanner Networks
• Graph spanners
• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
• A Framework for Computing the Greedy Spanner
• Experimental study of geometric t -spanners

This page was built for publication: Computing the greedy spanner in linear space