Fast constructions of lightweight spanners for general graphs

DOI10.1145/2836167MaRDI QIDQ4962607zbMATH OpenOpenAlexFDO

Authors Michael Elkin, Shay Solomon

Publication date 5 November 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

graph spannerslight spannerssparse graphs

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Abstract: To our knowledge, there are only two known algorithms for constructing sparse and light spanners for general graphs. One of them is the greedy algorithm of Alth$ddoto$fer et al. cite{ADDJS93}, analyzed by Chandra et al. in SoCG'92. The greedy algorithm consructs, for every emph{weighted} undirected $n$-vertex $m$-edge graph $G=(V,E)$ and any integer $kge1$, a $(2k-1)$-spanner with $O(n^{1+1/k})$ edges and weight $O(kcdot{n}^{(1+eps)/k})cdotomega(MST(G))$, for any $eps>0$. The drawback of the greedy algorithm is that it requires $O(mcdot(n^{1+1/k}+ncdotlogn))$ time. The other algorithm is due to Awerbuch et al. cite{ABP91}. It constructs $O(k)$-spanners with $O(kcdot{n}^{1+1/k}cdotLambda)$ edges, weight $O(k^{2}cdot{n}^{1/k}cdotLambda)cdotomega(MST(G))$, within time $O(mcdotkcdot{n}^{1/k}cdotLambda)$, where $Lambda$ is the logarithm of the aspect ratio of the graph. The running time of both these algorithms is unsatisfactory. Moreover, the usually faster algorithm of cite{ABP91} pays for the speedup by significantly increasing both the stretch, the sparsity, and the weight of the resulting spanner. In this paper we devise an efficient algorithm for constructing sparse and light spanners. Specifically, our algorithm constructs $((2k-1)cdot(1+eps))$-spanners with $O(kcdot{n}^{1+1/k})$ edges and weight $O(kcdot{n}^{1/k})cdotomega(MST(G))$, where $eps>0$ is an arbitrarily small constant. The running time of our algorithm is $O(kcdotm+minncdotlogn,mcdotalpha(n))$. Moreover, by slightly increasing the running time we can reduce the other parameters. These results address an open problem from the ESA'04 paper by Roditty and Zwick cite{RZ04}.

Recommendations

• Fast constructions of light-weight spanners for general graphs
• Light spanners
• Light spanners
• Near-optimal light spanners
• Near-optimal light spanners

Cited in

(17)

• Graph spanners: a tutorial review
• Constructing light spanners deterministically in near-linear time
• Very fast construction of bounded‐degree spanning graphs via the semi‐random graph process
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• scientific article; zbMATH DE number 2038725 (Why is no real title available?)
• Near-optimal light spanners
• Near-optimal light spanners
• The greedy spanner is existentially optimal
• Constructing Light Spanners Deterministically in Near-Linear Time
• Fast constructions of light-weight spanners for general graphs
• Online Spanners in Metric Spaces
• A unified framework for light spanners
• A unified framework of light spanners. I: Fast (yet optimal) constructions
• Spanner approximations in practice
• Online spanners in metric spaces
• An alternate proof of near-optimal light spanners
• Exact minimum weight spanners via column generation

This page was built for publication: Fast constructions of lightweight spanners for general graphs

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