Light Spanners

DOI10.1137/140979538zbMath1317.05183arXiv1404.7703OpenAlexW3037209702MaRDI QIDQ5499739

Michael Elkin, Shay Solomon, Ofer Neiman

Publication date: 31 July 2015

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

greedy algorithmgraph spannerslight spanners

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Related Items (5)

Light Euclidean Spanners with Steiner Points ⋮ 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 ⋮ Constructing light spanners deterministically in near-linear time

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Low-light trees, and tight lower bounds for Euclidean spanners
• On sparse spanners of weighted graphs
• Approximating the Single-Sink Link-Installation Problem in Network Design
• Light Spanners in Bounded Pathwidth Graphs
• Computing Lightweight Spanners Locally
• Distributed Computing: A Locality-Sensitive Approach
• Light graphs with small routing cost
• Light spanners for Snowflake Metrics
• NEW SPARSENESS RESULTS ON GRAPH SPANNERS
• New Doubling Spanners: Better and Simpler
• Algorithms – ESA 2004
• Optimal euclidean spanners
• Automata, Languages and Programming

This page was built for publication: Light Spanners