Additive spanners: a simple construction

DOI10.1007/978-3-319-08404-6_24zbMATH Open1417.05219arXiv1403.0178OpenAlexW1937137463MaRDI QIDQ3188902FDOQ3188902

Authors: Mathias Bæk Tejs Knudsen 

Publication date: 2 September 2014

Published in: Algorithm Theory – SWAT 2014 (Search for Journal in Brave)

Abstract: We consider additive spanners of unweighted undirected graphs. Let $G$ be a graph and $H$ a subgraph of $G$. The most na"ive way to construct an additive $k$-spanner of $G$ is the following: As long as $H$ is not an additive $k$-spanner repeat: Find a pair $(u,v)inH$ that violates the spanner-condition and a shortest path from $u$ to $v$ in $G$. Add the edges of this path to $H$. We show that, with a very simple initial graph $H$, this na"ive method gives additive $6$- and $2$-spanners of sizes matching the best known upper bounds. For additive $2$-spanners we start with $H=emptyset$ and end with $O(n^{3/2})$ edges in the spanner. For additive $6$-spanners we start with $H$ containing $lfloor{n}^{1/3}floor$ arbitrary edges incident to each node and end with a spanner of size $O(n^{4/3})$.

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

Recommendations

• Additive spanners in nearly quadratic time
• Additive spanners and \(({\alpha}, {\beta})\)-spanners
• New constructions of \(({\alpha}, {\beta})\)-spanners and purely additive spanners
• New additive spanners
• Low Distortion Spanners

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Cited In (22)

• Graph spanners: a tutorial review
• Title not available (Why is that?)
• Thorup-Zwick emulators are universally optimal hopsets
• Near-additive spanners and near-exact hopsets, a unified view
• A hierarchy of lower bounds for sublinear additive spanners
• The sparsest additive spanner via multiple weighted BFS trees
• Multi-priority graph sparsification
• The Sparsest Additive Spanner via Multiple Weighted BFS Trees
• New constructions of \(({\alpha}, {\beta})\)-spanners and purely additive spanners
• Low Distortion Spanners
• Lower bounds on sparse spanners, emulators, and diameter-reducing shortcuts
• A note on distance-preserving graph sparsification
• Additive spanners and \(({\alpha}, {\beta})\)-spanners
• Sparsification lower bound for linear spanners in directed graphs
• Improved weighted additive spanners
• New additive spanners
• On additive spanners in weighted graphs with local error
• New pairwise spanners
• New pairwise spanners
• Additive spanners in nearly quadratic time
• Small stretch pairwise spanners and approximate \(D\)-preservers
• Title not available (Why is that?)

This page was built for publication: Additive spanners: a simple construction

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