Additive Spanners in Nearly Quadratic Time

DOI10.1007/978-3-642-14165-2_40zbMath1288.68190MaRDI 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

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

Related Items

A Hierarchy of Lower Bounds for Sublinear Additive Spanners, The Sparsest Additive Spanner via Multiple Weighted BFS Trees, Sparse Weight Tolerant Subgraph for Single Source Shortest Path, Distributed construction of purely additive spanners, Approximate distance oracles with improved stretch for sparse graphs, New pairwise 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, Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences, Fault tolerant additive and \((\mu, \alpha)\)-spanners, Deterministic improved round-trip spanners, Source-wise round-trip spanners, On additive spanners in weighted graphs with local error, Small Stretch Pairwise Spanners and Approximate $D$-Preservers