Lightweight Near-Additive Spanners

Yuval Gitlitz, Ofer Neiman, Richard Spence

An $(\hat{I}\pm ,{\hat{I}}^2)$-spanner of a weighted graph $G=(V,E)$, is a subgraph $H$ such that for every $u,v\in V$, $d_G(u,v)\le d_H(u,v)\le \hat{I}\pm \cdot d_G(u,v)+{\hat{I}}^2$. The main parameters of interest…