Practical Construction of Metric t-Spanners

Gonzalo Navarro and Rodrigo Paredes

Let G(V,A) be a connected graph with a nonnegative cost function d: A -> R^+. Let d_G (u,v) be the cost of the cheapest path between u,v in V. A t-spanner of G is a subgraph G'(V,E), E subset of A, such that for all u,v in V, d_{G'} (u,v) <= t . d_G(u,v), t > 1. We focus on the metric space context, which means that A = V x V, d is a metric, and t <= 2. Several algorithms to build t-spanners are known, but they do not apply well to our case. We present four practical algorithms to build t-spanners with empirical O(n^2.24) time cost and O(n^1.13) edges. These algorithms are useful on general graphs as well.