Improved weighted additive spanners

DOI10.1007/S00446-022-00433-XMaRDI QIDQ6096039zbMATH OpenOpenAlexFDO

Authors Michael Elkin, Ofer Neiman

Publication date 11 September 2023

Published in Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

graph theorypure additive spanners

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Abstract: Graph spanners and emulators are sparse structures that approximately preserve distances of the original graph. While there has been an extensive amount of work on additive spanners, so far little attention was given to weighted graphs. Only very recently [ABSKS20] extended the classical +2 (respectively, +4) spanners for unweighted graphs of size $O(n^{3/2})$ (resp., $O(n^{7/5})$) to the weighted setting, where the additive error is $+2W$ (resp., $+4W$). This means that for every pair $u,v$, the additive stretch is at most $+2W_{u,v}$, where $W_{u,v}$ is the maximal edge weight on the shortest $u-v$ path. In addition, [ABSKS20] showed an algorithm yielding a $+8W_{max}$ spanner of size $O(n^{4/3})$, here $W_{max}$ is the maximum edge weight in the entire graph. In this work we improve the latter result by devising a simple deterministic algorithm for a $+(6+varepsilon)W$ spanner for weighted graphs with size $O(n^{4/3})$ (for any constant $varepsilon>0$), thus nearly matching the classical +6 spanner of size $O(n^{4/3})$ for unweighted graphs. Furthermore, we show a $+(2+varepsilon)W$ subsetwise spanner of size $O(ncdotsqrt|S|)$, improving the $+4W_{max}$ result of [ABSKS20] (that had the same size). We also show a simple randomized algorithm for a $+4W$ emulator of size $ildeO(n^{4/3})$. In addition, we show that our technique is applicable for very sparse additive spanners, that have linear size. For weighted graphs, we use a variant of our simple deterministic algorithm that yields a linear size $+ildeO(sqrtncdotW)$ spanner, and we also obtain a tradeoff between size and stretch. Finally, generalizing the technique of [DHZ00] for unweighted graphs, we devise an efficient randomized algorithm producing a $+2W$ spanner for weighted graphs of size $ildeO(n^{3/2})$ in $ildeO(n^2)$ time.

Recommendations

• scientific article; zbMATH DE number 7774272
• Weighted additive spanners
• scientific article; zbMATH DE number 7700598
• Improved purely additive fault-tolerant spanners
• Spanners of Additively Weighted Point Sets
• Spanners of additively weighted point sets
• Additive spanners in nearly quadratic time
• Fault-tolerant additive weighted geometric spanners
• The Sparsest Additive Spanner via Multiple Weighted BFS Trees
• The sparsest additive spanner via multiple weighted BFS trees

Cites work

• $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
• A Hierarchy of Lower Bounds for Sublinear Additive Spanners
• A trade-off between space and efficiency for routing tables
• Additive spanners: a simple construction
• All-Pairs Almost Shortest Paths
• Better distance preservers and additive spanners
• Computing almost shortest paths (extended abstract)
• Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Graph spanners
• Hopsets with constant hopbound, and applications to approximate shortest paths
• Improved weighted additive spanners
• Low distortion spanners
• New additive spanners
• New constructions of \(({\alpha}, {\beta})\)-spanners and purely additive spanners
• On additive spanners in weighted graphs with local error
• On efficient distributed construction of near optimal routing schemes
• On sparse spanners of weighted graphs
• Spanners and emulators with sublinear distance errors
• Sparse Distance Preservers and Additive Spanners
• The 4/3 additive spanner exponent is tight
• Very sparse additive spanners and emulators
• Weighted additive spanners

Cited in

(4)

• scientific article; zbMATH DE number 7774272 (Why is no real title available?)
• Improved weighted additive spanners
• Lightweight near-additive spanners
• Graph spanners for group Steiner distances

This page was built for publication: Improved weighted additive spanners

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