-spanners & MST
The greedy algorithm
The t-spanner vs the minimum spanning tree (MST)
The MST is one of the most well-known graph structures. A MST is a network connecting all vertices of a set in such a way, that the collective weight of the edges is as low as possible.
Figure 4: MSTs are spanners
A MST. Also a spanner. And for some t also a
Since any tree spans all the vertices in a set it is indeed a spanner. And since it must have a stretch factor, it is also a
-spanner for some
The reverse, however, is not true. A
-spanner is not nescessarily a MST nor even a tree. For one thing a
-spanner can have cycles.
Figure 5: A spanner is not nescesarily a MST
Graphs using the same set of points as figure 5.
Both are spanners but not trees.
The greedy algorithm presented in the following pages is nevertheless related to
Kruskal's greedy algorithm
for constructing MSTs. How, is explained in the greedy algorithm section.
-spanner is available in the exercises section.
Copyright 2005 Anja W-L, Nicolai M.A & Sune H