Additive spanners and (, )-spanners

DOI10.1145/1868237.1868242MaRDI QIDQ3188987zbMATH OpenOpenAlexFDO

Authors Surender Baswana, Telikepalli Kavitha, K. Mehlhorn, Seth Pettie

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

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

Recommendations

New constructions of $({\alpha}, {\beta})$-spanners and purely additive spanners
Local Computation of Nearly Additive Spanners
Additive spanners: a simple construction
Additive spanners in nearly quadratic time
Low Distortion Spanners

Cited in

(53)

Thorup-Zwick emulators are universally optimal hopsets
New pairwise spanners
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
Demand-aware network designs of bounded degree
The sparsest additive spanner via multiple weighted BFS trees
Fault tolerant approximate BFS structures with additive stretch
Fault tolerant additive and $(\mu, \alpha)$-spanners
Efficient algorithms for constructing $(1+\epsilon,\beta)$-spanners in the distributed and streaming models
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
Low distortion spanners
Rumor spreading with no dependence on conductance
On approximate distance labels and routing schemes with affine stretch
Additive spanners: a simple construction
Small stretch pairwise spanners and approximate D-preservers
Improved purely additive fault-tolerant spanners
Additive spanners in nearly quadratic time
Local Computation of Nearly Additive Spanners
A hierarchy of lower bounds for sublinear additive spanners
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
Near-additive spanners and near-exact hopsets, a unified view
The Sparsest Additive Spanner via Multiple Weighted BFS Trees
scientific article; zbMATH DE number 7238981 (Why is no real title available?)
Near-additive spanners in low polynomial deterministic CONGEST time
New (α, β) Spanners and Hopsets
Lower bounds on sparse spanners, emulators, and diameter-reducing shortcuts
Bypassing Erdős' girth conjecture: hybrid stretch and sourcewise spanners
(1 + εΒ) -spanner constructions for general graphs
Low Distortion Spanners
Efficient algorithms for constructing $(1+{\epsilon}, {\beta})$-spanners in the distributed and streaming models
New additive spanners
Graph spanners in the message-passing model
Distributed algorithms for ultrasparse spanners and linear size skeletons
Approximate distance oracles with improved stretch for sparse graphs
Communication-efficient distributed graph clustering and sparsification under duplication models
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
Restorable shortest path tiebreaking for edge-faulty graphs
On the edge crossings of the greedy spanner
New approximate distance oracles and their applications
Bounded degree spanners of the hypercube

This page was built for publication: Additive spanners and $({\alpha}, {\beta})$-spanners

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