On Pairwise Spanners

Marek Cygan, Fabrizio Grandoni, Telikepalli Kavitha

Given an undirected $n$-node unweighted graph $G=(V,E)$, a spanner with stretch function $f(\cdot )$ is a subgraph $H\subseteq G$ such that, if two nodes are at distance $d$ in $…