Fetching the paper…
Reading the bibliography…
Given an {\em unweighted} undirected graph $G = (V,E)$, and a pair of parameters $\epsilon > 0$, $\beta = 1,2,\ldots$, a subgraph $G' =(V,H)$, $H \subseteq E$, of $G$ is a {\em $(1+\epsilon,\beta)$-spanner} (aka, a {\em near-additive spanner}) of $G$ if for every $u,v \in V$, $$d_{G'}(u,v) \le (1+\epsilon)d_G(u,v) + \beta~.$$ It was shown in \cite{EP01} that for any $n$-vertex $G$ as above, and any $\epsilon > 0$ and $\kappa = 1,2,\ldots$, there exists a $(1+\epsilon,\beta)$-spanner $G'$ with $O_{\epsilon,\kappa}(n^{1+1/\kappa})$ edges, with $$\beta = \beta_{EP} = \left({{\log \kappa} \over \epsilon}\right)^{\log \kappa - 2}~.$$ This bound remains state-of-the-art, and its dependence on $\epsilon$ (for the case of small $\kappa$) was shown to be tight in \cite{ABP18}.
Graph spanners
D. Peleg and A. A. Schaffer · 1989
Earlier work this paper cites.
Generating sparse spanners for weighted graphs
Ingo Althöfer, Gautam Das, David P. Dobkin, and Deborah Joseph · 1990
Earlier work this paper cites.
High-probability parallel transitive-closure algorithms
Jeffrey D. Ullman and Mihalis Yannakakis · 1991
Earlier work this paper cites.
Routing with polynomial communication-space trade-off
Baruch Awerbuch and David Peleg · 1992
Earlier work this paper cites.
Near-linear cost sequential and distribured constructions of sparse neighborhood covers
Baruch Awerbuch, Bonnie Berger, Lenore Cowen, and David Peleg · 1993
Earlier work this paper cites.
Fast algorithms for constructing t-spanners and paths with stretch t
Edith Cohen · 1993
Earlier work this paper cites.
A linear-processor polylog-time algorithm for shortest paths in planar graphs
Philip N. Klein and Sairam Subramanian · 1993
Earlier work this paper cites.
Polylog-time and near-linear work approximation scheme for undirected shortest paths
Edith Cohen · 1994
Earlier work this paper cites.
An optimal randomised logarithmic time connectivity algorithm for the EREW PRAM
S. Halperin and U. Zwick · 1996
Earlier work this paper cites.
Unpublished
S. Halperin and U. Zwick · 1996
Earlier work this paper cites.
Fast algorithms for constructing t t -spanners and paths with stretch t t
E. Cohen · 1998
Earlier work this paper cites.
Fast estimation of diameter and shortest paths (without matrix multiplication)
D. Aingworth, C. Chekuri, P. Indyk, and R. Motwani · 1999
Earlier work this paper cites.
Time-work tradeoffs of the single-source shortest paths problem
Hanmao Shi and Thomas H. Spencer · 1999
Earlier work this paper cites.
All-pairs almost shortest paths
D. Dor, S. Halperin, and U. Zwick · 2000
Earlier work this paper cites.
Computing almost shortest paths
M. Elkin · 2001
Cited alongside, same era.
( 1 + ϵ , β ) (1+\epsilon,\beta) -spanner constructions for general graphs
M. Elkin and D. Peleg · 2001
Cited alongside, same era.
Approximate distance oracles
M. Thorup and U. Zwick · 2001
Cited alongside, same era.
Lower bounds for additive spanners, emulators, and more
D. Woodruff · 2001
Cited alongside, same era.
Compact roundtrip routing in directed networks
L. J. Cowen and C. G. Wagner · 2004
Cited alongside, same era.
New constructions of ( α , β ) (\alpha,\beta) -spanners and purely additive spanners
S. Baswana, T. Kavitha, K. Mehlhorn, and S. Pettie · 2005
Cited alongside, same era.
New additive spanners
Shiri Chechik · 2013
Later among the works it cites.
Decremental single-source shortest paths on undirected graphs in near-linear total update time
Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai · 2014
Later among the works it cites.
Improved parallel algorithms for spanners and hopsets
Gary L. Miller, Richard Peng, Adrian Vladu, and Shen Chen Xu · 2015
Later among the works it cites.
The 4/3 additive spanner exponent is tight
Amir Abboud and Greg Bodwin · 2016
Later among the works it cites.
Hopsets with constant hopbound, and applications to approximate shortest paths
Michael Elkin and Ofer Neiman · 2016
Later among the works it cites.
A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai · 2016
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Sparse source-wise and pair-wise distance preservers
D. Coppersmith and M. Elkin · 2005
Cited alongside, same era.
Deterministic constructions of approximate distance oracles and spanners
L. Roditty, M. Thorup, and U. Zwick · 2005
Cited alongside, same era.
Efficient algorithms for constructing ( 1 + ϵ , β ) (1+\epsilon,\beta) -spanners in the distributed and streaming models
M. Elkin and J. Zhang · 2006
Cited alongside, same era.
Spanners and emulators with sublinear distance errors
M. Thorup and U. Zwick · 2006
Cited alongside, same era.
Low distortion spanners
S. Pettie · 2007
Cited alongside, same era.
Distributed algorithms for ultrasparse spanners and linear size skeletons
Seth Pettie · 2008
Cited alongside, same era.
Later among the works it cites.
Efficient algorithms for constructing very sparse spanners and emulators
Michael Elkin and Ofer Neiman · 2017
Later among the works it cites.
A hierarchy of lower bounds for sublinear additive spanners
Amir Abboud, Greg Bodwin, and Seth Pettie · 2018
Later among the works it cites.
Almost shortest paths and PRAM distance oracles in weighted graphs
Michael Elkin, Yuval Gitlitz, and Ofer Neiman · 2019
Later among the works it cites.
Near-additive spanners in low polynomial deterministic CONGEST time
Michael Elkin and Shaked Matar · 2019
Later among the works it cites.
Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC
Michael Elkin and Ofer Neiman · 2019
Later among the works it cites.
Thorup-zwick emulators are universally optimal hopsets
Shang-En Huang and Seth Pettie · 2019
Later among the works it cites.
New ( α \alpha , β \beta ) spanners and hopsets spanners and hopsets
Uri Ben-Levy and Merav Parter · 2020
Closest in time.