Near-additive spanners and near-exact hopsets, a unified view

MaRDI QIDQ5011874zbMATH OpenFDO

Authors Michael Elkin, Ofer Neiman

Publication date 30 August 2021

Full work available at URL https://arxiv.org/abs/2001.07477, http://bulletin.eatcs.org/index.php/beatcs/article/view/608/624

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Additive spanners and \(({\alpha}, {\beta})\)-spanners
• $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
• New constructions of \(({\alpha}, {\beta})\)-spanners and purely additive spanners
• (1 + εΒ) -spanner constructions for general graphs
• Additive spanners: a simple construction

Cited in

(7)

• Thorup-Zwick emulators are universally optimal hopsets
• A Hierarchy of Lower Bounds for Sublinear Additive Spanners
• New (α, β) Spanners and Hopsets
• Lower bounds on sparse spanners, emulators, and diameter-reducing shortcuts
• New tradeoffs for decremental approximate all-pairs shortest paths
• Massively parallel algorithms for approximate shortest paths
• Additive sparsification of CSPs

This page was built for publication: Near-additive spanners and near-exact hopsets, a unified view

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