Balancing Degree, Diameter, and Weight in Euclidean Spanners

DOI10.1137/120901295zbMath1305.05048arXiv1108.6022OpenAlexW1972027042MaRDI QIDQ2935264

Shay Solomon, Michael Elkin

Publication date: 22 December 2014

Published in: SIAM Journal on Discrete Mathematics, Algorithms – ESA 2010 (Search for Journal in Brave)

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

zbMATH Keywords

Euclidean spacesdoubling metricsEuclidean spanners

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items (8)

Dynamic Tree Shortcut with Constant Degree ⋮ Minimum weight Euclidean \((1+\varepsilon)\)-spanners ⋮ New Doubling Spanners: Better and Simpler ⋮ Forward-secure encryption with fast forwarding ⋮ Minimum weight Euclidean \((1+\varepsilon)\)-spanners ⋮ Light Euclidean Spanners with Steiner Points ⋮ Sparse fault-tolerant spanners for doubling metrics with bounded hop-diameter or degree ⋮ Local routing in a tree metric \(1\)-spanner

This page was built for publication: Balancing Degree, Diameter, and Weight in Euclidean Spanners