New additive spanners

DOI10.1137/1.9781611973105.36MaRDI QIDQ5741744zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• New constructions of \(({\alpha}, {\beta})\)-spanners and purely additive spanners
• Additive spanners: a simple construction
• Additive spanners in nearly quadratic time
• Additive spanners and \(({\alpha}, {\beta})\)-spanners
• New pairwise spanners

Cited in

(38)

• New pairwise spanners
• NP-hardness and fixed-parameter tractability of the minimum spanner problem
• Fault-tolerant approximate shortest-path trees
• Graph spanners: a tutorial review
• A fast algorithm for source-wise round-trip spanners
• Sparsification lower bound for linear spanners in directed graphs
• A note on distance-preserving graph sparsification
• Multiple-edge-fault-tolerant approximate shortest-path trees
• Fault tolerant approximate BFS structures with additive stretch
• 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
• New constructions of \(({\alpha}, {\beta})\)-spanners and purely additive spanners
• New Doubling Spanners: Better and Simpler
• Additive spanners: a simple construction
• Small stretch pairwise spanners and approximate D-preservers
• Additive spanners in nearly quadratic time
• scientific article; zbMATH DE number 1969385 (Why is no real title available?)
• A hierarchy of lower bounds for sublinear additive spanners
• $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
• Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
• scientific article; zbMATH DE number 7238981 (Why is no real title available?)
• Lower bounds on sparse spanners, emulators, and diameter-reducing shortcuts
• Bypassing Erdős' girth conjecture: hybrid stretch and sourcewise spanners
• New Doubling Spanners: Better and Simpler
• The 4/3 additive spanner exponent is tight
• Approximate distance oracles with improved stretch for sparse graphs
• Communication-efficient distributed graph clustering and sparsification under duplication models
• Improved weighted additive spanners
• Multi-priority graph sparsification
• Almost-optimal sublinear additive spanners
• Improved sourcewise roundtrip spanners with constant stretch
• Additive spanner lower bounds with optimal inner graph structure
• Lightweight near-additive spanners
• Additive sparsification of CSPs
• New approximate distance oracles and their applications
• Bounded degree spanners of the hypercube

This page was built for publication: New additive spanners

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5741744)