New Additive Spanners

DOI10.1137/1.9781611973105.36zbMath1412.68165OpenAlexW4214510568MaRDI QIDQ5741744

Shiri Chechik

Publication date: 15 May 2019

Published in: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973105.36

Mathematics Subject Classification ID

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

Related Items (27)

On resilient graph spanners ⋮ 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 ⋮ Communication-efficient distributed graph clustering and sparsification under duplication models ⋮ Vertex fault tolerant additive spanners ⋮ Improved weighted additive spanners ⋮ New pairwise spanners ⋮ Multi-priority graph sparsification ⋮ 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 ⋮ NP-hardness and fixed-parameter tractability of the minimum spanner problem ⋮ A fast algorithm for source-wise round-trip spanners ⋮ Fault-tolerant approximate shortest-path trees ⋮ Unnamed Item ⋮ Sparsification lower bound for linear spanners in directed graphs ⋮ A note on distance-preserving graph sparsification ⋮ 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: New Additive Spanners