New $(\alpha ,\beta )$ Spanners and Hopsets

Uri Ben-Levy, Merav Parter

An $f(d)$-spanner of an unweighted $n$-vertex graph $G=(V,E)$ is a subgraph $H$ satisfying that $dis{t}_H(u,v)$ is at most $f(dis{t}_G(u,v))$ for every $u,v\in V$. We present new sp…