Improved weighted additive spanners

DOI10.1007/s00446-022-00433-xarXiv2008.09877OpenAlexW3210100236MaRDI QIDQ6096039

Ofer Neiman, Michael Elkin, Unnamed Author

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)

Related Items

Improved weighted additive spanners

Cites Work

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

This page was built for publication: Improved weighted additive spanners