Spanner Approximations in Practice

Markus Chimani, Finn Stutzenstein

A multiplicative $\alpha$-spanner $H$ is a subgraph of $G=(V,E)$ with the same vertices and fewer edges that preserves distances up to the factor $\alpha$, i.e., $d_H(u,v)\leqα\cdot d_G(u,v)…