The Greedy Spanner is Existentially Optimal

DOI10.1145/2933057.2933114zbMath1376.68108arXiv1605.06852OpenAlexW2398255676MaRDI QIDQ5361910

Shay Solomon, Arnold Filtser

Publication date: 29 September 2017

Published in: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1605.06852

zbMATH Keywords

greedy algorithmgraph spannergreedy spannerdoubling metriclight spanner

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (10)

On additive spanners in weighted graphs with local error ⋮ Geometric spanning trees minimizing the Wiener index ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Graph spanners: a tutorial review ⋮ The Greedy Spanner Is Existentially Optimal ⋮ Constructing Light Spanners Deterministically in Near-Linear Time ⋮ On notions of distortion and an almost minimum spanning tree with constant average distortion ⋮ Light spanners for high dimensional norms via stochastic decompositions

This page was built for publication: The Greedy Spanner is Existentially Optimal