Improved weighted additive spanners

DOI10.1007/S00446-022-00433-XarXiv2008.09877OpenAlexW3210100236MaRDI QIDQ6096039FDOQ6096039

Ofer Neiman, Michael Elkin, Author name not available (Why is that?)

Publication date: 11 September 2023

Published in: Distributed Computing (Search for Journal in Brave)

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.

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

zbMATH Keywords

graph theorypure additive spanners

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (2)

• Title not available (Why is that?)
• Improved weighted additive spanners

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Spanners of Additively Weighted Point Sets 👍 👎
• Spanners of additively weighted point sets 👍 👎
• Improved Purely Additive Fault-Tolerant Spanners 👍 👎
• Additive Spanners in Nearly Quadratic Time 👍 👎
• Fault-tolerant additive weighted geometric spanners 👍 👎
• The sparsest additive spanner via multiple weighted BFS trees 👍 👎
• Weighted additive spanners 👍 👎
• The Sparsest Additive Spanner via Multiple Weighted BFS Trees 👍 👎

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)