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