Additive Spanners in Nearly Quadratic Time

DOI10.1007/978-3-642-14165-2_40zbMath1288.68190OpenAlexW1607700260MaRDI QIDQ3587400

David P. Woodruff

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

Mathematics Subject Classification ID

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