Light spanners

DOI10.1137/140979538MaRDI QIDQ5499739zbMATH OpenOpenAlexFDO

Authors Michael Elkin, Ofer Neiman, Shay Solomon

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

graph spannersgreedy algorithmlight spanners

Mathematics Subject Classification ID

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

Abstract: A $t$-spanner of a weighted undirected graph $G=(V,E)$, is a subgraph $H$ such that $d_H(u,v)letcdot{d}_G(u,v)$ for all $u,vinV$. The sparseness of the spanner can be measured by its size (the number of edges) and weight (the sum of all edge weights), both being important measures of the spanner's quality -- in this work we focus on the latter. Specifically, it is shown that for any parameters $kge1$ and $epsilon>0$, any weighted graph $G$ on $n$ vertices admits a $(2k-1)cdot(1+epsilon)$-stretch spanner of weight at most $w(MST(G))cdot{O}_{e}psilon(k{n}^{1/k}/logk)$, where $w(MST(G))$ is the weight of a minimum spanning tree of $G$. Our result is obtained via a novel analysis of the classic greedy algorithm, and improves previous work by a factor of $O(logk)$.

Recommendations

• Light spanners
• Near-optimal light spanners
• Near-optimal light spanners
• Fast constructions of light-weight spanners for general graphs
• NEW SPARSENESS RESULTS ON GRAPH SPANNERS

Cites work

• Algorithms – ESA 2004
• Approximating the single-sink link-installation problem in network design
• Automata, Languages and Programming
• Computing Lightweight Spanners Locally
• Distributed Computing: A Locality-Sensitive Approach
• scientific article; zbMATH DE number 1670877 (Why is no real title available?)
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 1263225 (Why is no real title available?)
• scientific article; zbMATH DE number 2038725 (Why is no real title available?)
• scientific article; zbMATH DE number 1532274 (Why is no real title available?)
• Light graphs with small routing cost
• Light spanners for snowflake metrics
• Light spanners in bounded pathwidth graphs
• Low-light trees, and tight lower bounds for Euclidean spanners
• New Doubling Spanners: Better and Simpler
• NEW SPARSENESS RESULTS ON GRAPH SPANNERS
• On sparse spanners of weighted graphs
• Optimal Euclidean spanners, really short, thin and lanky

Cited in

(23)

• On sparse spanners of weighted graphs
• Constructing light spanners deterministically in near-linear time
• On notions of distortion and an almost minimum spanning tree with constant average distortion
• Light spanners in bounded pathwidth graphs
• Near-optimal light spanners
• Near-optimal light spanners
• Light spanners for snowflake metrics
• The greedy spanner is existentially optimal
• Fast constructions of lightweight spanners for general graphs
• Generating sparse spanners for weighted graphs
• Constructing Light Spanners Deterministically in Near-Linear Time
• Light spanners
• Small Stretch Pairwise Spanners
• Algorithms – ESA 2004
• Fast constructions of light-weight spanners for general graphs
• Light Euclidean Spanners with Steiner Points
• Simple approximations for general spanner problems
• Light, reliable spanners
• Stable roommates spanner
• Spanner approximations in practice
• An alternate proof of near-optimal light spanners
• Light Euclidean Steiner spanners in the plane
• Exact minimum weight spanners via column generation

This page was built for publication: Light spanners

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