Fetching the paper…
Reading the bibliography…
For a positive integer $t$ and a graph $G$, an additive $t$-spanner of $G$ is a spanning subgraph in which the distance between every pair of vertices is at most the original distance plus $t$.
Additive spanners in nearly quadratic time
D. P. Woodruff · 1903
Earlier work this paper cites.
Extremal problems in graph theory
P. Erdős · 1964
Earlier work this paper cites.
Complexity of network synchronization
B. Awerbuch · 1985
Earlier work this paper cites.
Graph spanners
D. Peleg and A. A. Schäffer · 1989
Earlier work this paper cites.
An optimal synchronizer for the hypercube
D. Peleg and J. D. Ullman · 1989
Earlier work this paper cites.
A trade-off between space and efficiency for routing tables
D. Peleg and E. Upfal · 1989
Earlier work this paper cites.
Additive spanners for hypercubes
A. Liestman and T. Shermer · 1991
Earlier work this paper cites.
On sparse spanners of weighted graphs
I. Althöfer, G. Das, D. Dobkin, D. Joseph, and J. Soares · 1993
Earlier work this paper cites.
Additive graph spanners
A. L. Liestman and T. C. Shermer · 1993
Earlier work this paper cites.
NP-completeness of minimum spanner problems
L. Cai · 1994
Earlier work this paper cites.
Spanners in graphs of bounded degree
L. Cai and M. Keil · 1994
Earlier work this paper cites.
Generating sparse 2-spanners
G. Kortsarz and D. Peleg · 1994
Earlier work this paper cites.
Tree spanners
L. Cai and D. G. Corneil · 1995
Earlier work this paper cites.
Tree 3-spanners on interval, permutation and regular bipartite graphs
M. S. Madanlal, G. Venkatesan, and C. P. Rangan · 1996
Earlier work this paper cites.
NP-completeness results for minimum planar spanners
U. Brandes and D. Handke · 1997
Earlier work this paper cites.
Restrictions of minimum spanner problems
G. Venkatesan, U. Rotics, M. S. Madanlal, J. A. Makowsky, and C. P. Rangan · 1997
Cited alongside, same era.
Fast algorithms for constructing t t -spanners and paths with stretch t t
E. Cohen · 1998
Cited alongside, same era.
Fast estimation of diameter and shortest paths (without matrix multiplication)
D. Aingworth, C. Chekuri, P. Indyk, and R. Motwani · 1999
Cited alongside, same era.
Polylog-time and near-linear work approximation scheme for undirected shortest paths
E. Cohen · 2000
Cited alongside, same era.
A PTAS for the sparsest 2-spanner of 4-connected planar triangulations
W. Duckworth, N. C Wormald, and M. Zito · 2003
Cited alongside, same era.
Additive tree spanners
D. Kratsch, H. Le, H. Müller, E. Prisner, and D. Wagner · 2003
Cited alongside, same era.
Parameterized Complexity Theory
J. Flum and M. Grohe · 2006
Later among the works it cites.
Invitation to Fixed Parameter Algorithms
R. Niedermeier · 2006
Later among the works it cites.
Spanners and emulators with sublinear distance errors
M. Thorup and U. Zwick · 2006
Later among the works it cites.
Lower bounds for additive spanners, emulators, and more
D. P. Woodruff · 2006
Later among the works it cites.
The hardness of approximating spanner problems
M. Elkin and D. Peleg · 2007
Later among the works it cites.
Low distortion spanners
S. Pettie · 2009
Later among the works it cites.
Additive spanners and ( α \alpha , β \beta )-spanners
S. Baswana, T. Kavitha, K. Mehlhorn, and S. Pettie · 2010
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Compact roundtrip routing in directed networks
L. J. Cowen and C. G. Wagner · 2004
Cited alongside, same era.
( 1 + ϵ , β ) (1+\epsilon,\beta) -spanner constructions for general graphs
M. Elkin and D. Peleg · 2004
Cited alongside, same era.
Sparse distance preservers and additive spanners
B. Bollobás, D. Coppersmith, and M. Elkin · 2005
Cited alongside, same era.
Additive sparse spanners for graphs with bounded length of largest induced cycle
V. D. Chepoi, F. F. Dragan, and C. Yan · 2005
Cited alongside, same era.
Computing almost shortest paths
M. Elkin · 2005
Cited alongside, same era.
Approximating k k -spanner problems for k > 2 k>2
M. Elkin and D. Peleg · 2005
Cited alongside, same era.
Later among the works it cites.
Approximation of minimum weight spanners for sparse graphs
F. F. Dragan, F. V. Fomin, and P. A. Golovach · 2011
Later among the works it cites.
New additive spanners
S. Chechik · 2013
Later among the works it cites.
Additive spanners: A simple construction
M. B. T. Knudsen · 2014
Later among the works it cites.
Parameterized Algorithms
M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh · 2015
Later among the works it cites.
The 4/3 additive spanner exponent is tight
A. Abboud and G. Bodwin · 2017
Later among the works it cites.
Parameterized algorithms for survivable network design with uniform demands
J. Bang-Jensen, M. Basavaraju, K. V. Klinkby, P. Misra, M. S. Ramanujan, S. Saurabh, and M. Zehavi · 2018
Later among the works it cites.
Efficient algorithms for constructing very sparse spanners and emulators
M. Elkin and O. Neiman · 2018
Later among the works it cites.
NP-hardness and fixed-parameter tractability of the minimum spanner problem
Y. Kobayashi · 2018
Later among the works it cites.