Improved Purely Additive Fault-Tolerant Spanners

Davide Bilò, Fabrizio Grandoni, Luciano Gualà +2

Let $G$ be an unweighted $n$-node undirected graph. A \emph{$\beta$-additive spanner} of $G$ is a spanning subgraph $H$ of $G$ such that distances in $H$ are stretched at most by an ad…