The Norms of Graph Spanners

Eden Chlamtáč, Michael Dinitz, Thomas Robinson

A $t$-spanner of a graph $G$ is a subgraph $H$ in which all distances are preserved up to a multiplicative $t$ factor. A classical result of Althöfer et al. is that for every integ…