###
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.