Weighted Additive Spanners

DOI10.1007/978-3-030-60440-0_32MaRDI QIDQ6334991arXivFDO

Authors Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Stephen G. Kobourov, Richard Spence

Publication date 15 February 2020

Published in arXiv

Full work available at URL https://doi.org/10.1007/978-3-030-60440-0_32

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

arXiv classification

cs.DMcs.DSmath.CO

Abstract: A emph{spanner} of a graph $G$ is a subgraph $H$ that approximately preserves shortest path distances in $G$. Spanners are commonly applied to compress computation on metric spaces corresponding to weighted input graphs. Classic spanner constructions can seamlessly handle edge weights, so long as error is measured emph{multiplicatively}. In this work, we investigate whether one can similarly extend constructions of spanners with purely emph{additive} error to weighted graphs. These extensions are not immediate, due to a key lemma about the size of shortest path neighborhoods that fails for weighted graphs. Despite this, we recover a suitable amortized version, which lets us prove direct extensions of classic $+2$ and $+4$ unweighted spanners (both all-pairs and pairwise) to $+2W$ and $+4W$ weighted spanners, where $W$ is the maximum edge weight. Specifically, we show that a weighted graph $G$ contains all-pairs (pairwise) $+2W$ and $+4W$ weighted spanners of size $O(n^{3/2})$ and $widetildeO(n^{7/5})$ ($O(n{p}^{1/3})$ and $O(n{p}^{2/7})$) respectively. For a technical reason, the $+6$ unweighted spanner becomes a $+8W$ weighted spanner; closing this error gap is an interesting remaining open problem. That is, we show that $G$ contains all-pairs (pairwise) $+8W$ weighted spanners of size $O(n^{4/3})$ ($O(n{p}^{1/4})$).

This page was built for publication: Weighted Additive Spanners

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