Construction of Minimum-Weight Spanners

Spanners are sparse subgraphs that preserve distances up to
a given factor in the underlying graph. Recently spanners have found
important practical applications in metric space searching andmessage
distribution in networks. These applications use some variant of the so-
called greedy algorithm for constructing the spanner — an algorithm that
mimics Kruskal’s minimum spanning tree algorithm. Greedy spanners
have nice theoretical properties, but their practical performance with
respect to total weight is unknown. In this paper we give an exact al-
gorithm for constructing minimum-weight spanners in arbitrary graphs.
By using the solutions (andlower bounds) from this algorithm, we ex-
perimentally evaluate the performance of the greedy algorithm for a set
of realistic problem instances