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.