Distributed Spanner Approximation

We address the fundamental network design problem of constructing approximate minimum spanners. Our contributions are for the distributed setting, providing both algorithmic and hardness results. Our main hardness result shows that an $\alpha$-approximation for the minimum directed $k$-spanner probl... View More