Practical Construction of Metric t-Spanners

摘要

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 G V. A t-spanner of G is a subgraph G'(V, E), E is contained in A, such that any u, v ∈ 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 seem to apply well to our case. We present four practical algorithms to build t-spanners with empirical time costs of the form C_t · n~2 + ((0.1...0.2)/(t-1)) and number of edges of the form C_e · n~1 + ((0.1...0.2)/(t-1)). These algorithms are useful on general graphs as well.