Spanner Approximations in Practice
share
A multiplicative α-spanner H is a subgraph of G=(V,E) with the same vertices and fewer edges that preserves distances up to the factor α, i.e., d_H(u,v)≤α· d_G(u,v) for all vertices u, v. While many algorithms have been developed to find good spanners in terms of approximation guarantees, no experimental studies comparing different approaches exist. We implemented a rich selection of those algorithms and evaluate them on a variety of instances regarding, e.g., their running time, sparseness, lightness, and effective stretch.
READ FULL TEXT