Additive spanners and (α, β)-spanners

DOI10.1145/1868237.1868242zbMath1295.05094OpenAlexW2099237198MaRDI QIDQ3188987

Seth Pettie, Kurt Mehlhorn, Surender Baswana, Telikepalli Kavitha

Publication date: 9 September 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1868237.1868242

zbMATH Keywords

spannermetric embedding

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (33)

On resilient graph spanners ⋮ Thorup-Zwick emulators are universally optimal hopsets ⋮ Source-wise round-trip spanners ⋮ Small Stretch Pairwise Spanners and Approximate $D$-Preservers ⋮ Improved Purely Additive Fault-Tolerant Spanners ⋮ A Hierarchy of Lower Bounds for Sublinear Additive Spanners ⋮ Deterministic improved round-trip spanners ⋮ On additive spanners in weighted graphs with local error ⋮ Communication-efficient distributed graph clustering and sparsification under duplication models ⋮ Demand-aware network designs of bounded degree ⋮ Vertex fault tolerant additive spanners ⋮ New pairwise spanners ⋮ Rumor Spreading with No Dependence on Conductance ⋮ Multi-priority graph sparsification ⋮ The sparsest additive spanner via multiple weighted BFS trees ⋮ Fault tolerant approximate BFS structures with additive stretch ⋮ Lower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing Shortcuts ⋮ Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners ⋮ Distributed construction of purely additive spanners ⋮ Graph spanners: a tutorial review ⋮ A fast algorithm for source-wise round-trip spanners ⋮ Fault-tolerant approximate shortest-path trees ⋮ Unnamed Item ⋮ Distributed algorithms for ultrasparse spanners and linear size skeletons ⋮ Sparsification lower bound for linear spanners in directed graphs ⋮ A note on distance-preserving graph sparsification ⋮ The Sparsest Additive Spanner via Multiple Weighted BFS Trees ⋮ On Approximate Distance Labels and Routing Schemes with Affine Stretch ⋮ Approximate distance oracles with improved stretch for sparse graphs ⋮ Multiple-edge-fault-tolerant approximate shortest-path trees ⋮ Bounded degree spanners of the hypercube ⋮ Toward Tight Approximation Bounds for Graph Diameter and Eccentricities ⋮ Fault tolerant additive and \((\mu, \alpha)\)-spanners

This page was built for publication: Additive spanners and (α, β)-spanners