Additive Spanners in Nearly Quadratic Time
From MaRDI portal
Publication:3587400
DOI10.1007/978-3-642-14165-2_40zbMath1288.68190OpenAlexW1607700260MaRDI QIDQ3587400
Publication date: 7 September 2010
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-14165-2_40
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (16)
Source-wise round-trip spanners ⋮ Small Stretch Pairwise Spanners and Approximate $D$-Preservers ⋮ A Hierarchy of Lower Bounds for Sublinear Additive Spanners ⋮ Deterministic improved round-trip spanners ⋮ On additive spanners in weighted graphs with local error ⋮ New pairwise spanners ⋮ The sparsest additive spanner via multiple weighted BFS trees ⋮ Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences ⋮ Distributed construction of purely additive spanners ⋮ Graph spanners: a tutorial review ⋮ A fast algorithm for source-wise round-trip spanners ⋮ Sparsification lower bound for linear spanners in directed graphs ⋮ The Sparsest Additive Spanner via Multiple Weighted BFS Trees ⋮ Approximate distance oracles with improved stretch for sparse graphs ⋮ Sparse Weight Tolerant Subgraph for Single Source Shortest Path ⋮ Fault tolerant additive and \((\mu, \alpha)\)-spanners
This page was built for publication: Additive Spanners in Nearly Quadratic Time