The Sparsest Additive Spanner via Multiple Weighted BFS Trees

DOI10.4230/LIPICS.OPODIS.2018.7MaRDI QIDQ5091078zbMATH OpenOpenAlexFDO

Authors Keren Censor-Hillel, Ami Paz, Noam Ravid

Publication date 21 July 2022

Full work available at URL https://dblp.uni-trier.de/db/journals/corr/corr1811.html#abs-1811-01997

zbMATH Keywords

additive spannerscongest modeldistributed graph algorithmsweighted BFS trees

Mathematics Subject Classification ID

Distributed systems (68M14) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Recommendations

• The sparsest additive spanner via multiple weighted BFS trees
• Additive spanners and \(({\alpha}, {\beta})\)-spanners
• Additive spanners in nearly quadratic time
• On the locality of distributed sparse spanner construction
• Additive spanners: a simple construction

Cites work

• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• A deterministic distributed algorithm for exact weighted all-pairs shortest paths in \(\tilde{O}(n^{3/2})\) rounds
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
• A trade-off between space and efficiency for routing tables
• Additive spanners and \(({\alpha}, {\beta})\)-spanners
• Additive spanners in nearly quadratic time
• Additive spanners: a simple construction
• An Optimal Synchronizer for the Hypercube
• Compact routing schemes with improved stretch
• Computing almost shortest paths
• Congested clique algorithms for graph spanners
• Derandomizing distributed algorithms with small messages: spanners and dominating set
• Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time
• Distributed algorithms for ultrasparse spanners and linear size skeletons
• Distributed approximation algorithms for weighted shortest paths
• Distributed Computing: A Locality-Sensitive Approach
• Distributed distance computation and routing with small messages
• Distributed Spanner Approximation
• Distributed verification and hardness of distributed approximation
• Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
• Efficient distributed source detection with limited bandwidth
• Error Amplification for Pairwise Spanner Lower Bounds
• Fast deterministic distributed algorithms for sparse spanners
• Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
• Global computation in a poorly connected world
• Graph spanners
• Hopsets with constant hopbound, and applications to approximate shortest paths
• Improved deterministic distributed construction of spanners
• Improved distributed algorithms for exact shortest paths
• Improved Distributed Approximate Matching
• Local Computation of Nearly Additive Spanners
• Near-linear lower bounds for distributed distance computations, even in sparse networks
• New pairwise spanners
• On the locality of distributed sparse spanner construction
• Optimal distributed all pairs shortest paths and applications
• The 4/3 additive spanner exponent is tight
• The sparsest additive spanner via multiple weighted BFS trees

Cited in

(4)

• Additive sparse spanners for graphs with bounded length of largest induced cycle
• An FPT Algorithm for Minimum Additive Spanner Problem.
• scientific article; zbMATH DE number 7774272 (Why is no real title available?)
• Improved weighted additive spanners

This page was built for publication: The Sparsest Additive Spanner via Multiple Weighted BFS Trees

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