New (α, β) Spanners and Hopsets

DOI10.1137/1.9781611975994.104MaRDI QIDQ5146883zbMATH OpenOpenAlexFDO

Authors Uri Ben-Levy, M. Parter

Publication date 2 February 2021

Published in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• New constructions of \(({\alpha}, {\beta})\)-spanners and purely additive spanners
• Additive spanners and \(({\alpha}, {\beta})\)-spanners
• Near-additive spanners and near-exact hopsets, a unified view
• NEW SPARSENESS RESULTS ON GRAPH SPANNERS
• $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
• (1 + εΒ) -spanner constructions for general graphs
• New pairwise spanners
• New pairwise spanners
• On Pairwise Spanners
• scientific article; zbMATH DE number 5054175

Cited in

(7)

• Graph spanners: a tutorial review
• (1 + εΒ) -spanner constructions for general graphs
• Approximate distance oracles with improved stretch for sparse graphs
• Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics
• On the size overhead of pairwise spanners
• A unified framework for hopsets
• Approximation algorithms for optimal hopsets

This page was built for publication: New (α, β) Spanners and Hopsets

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