Warning: Undefined variable $PHP_SELF in /customers/9/8/1/usmart.dk/httpd.www/bachelor/index.php on line 2
Warning: Undefined array key "word" in /customers/9/8/1/usmart.dk/httpd.www/bachelor/index.php on line 5
Warning: Undefined array key "svar" in /customers/9/8/1/usmart.dk/httpd.www/bachelor/index.php on line 6
Warning: Undefined array key "valg" in /customers/9/8/1/usmart.dk/httpd.www/bachelor/index.php on line 7
Spanners
A greedy algorithm operates by constantly choosing a locally optimal solution. But what is an optimal t-spanner?
If the spanner is to be used as a construction plan for oil pipes, the collective length of the system might be of interest due to construction and maintenance expenses. The ability of the system to remain operable if a pipe is blocked might also be relevant.
Depending on the type of problem the t-spanner is used to solve, the quality measures could be:
The weight of the graph (collective weight of the edges).
The size of the graph (number of edges).
The degree of the graph (maximum vertex degree).
Fault tolerance, Diameter, Load factor, Number of crossings etc..
Which, then, of these properties does the greedy algorithm possess?
Figure 7: Testing the properties of the greedy algorithm
A set of vertices
The t-spanner for t=1.5 constructed by the greedy algorithm.
A t-spanner for t=1.5 with minimum weight and minimum size.
Also a minimum spanning tree.
The above example shows that the graph created by the greedy algorithm is not necessarily a minimum weight nor a minimum size graph.
In fact, the greedy algorithm only guarantees that the graph is indeed a t-spanner.
Then what are spanners good for?
The t-spanner is a sparse approximation of the complete graph. For reasonable values of t, the spanner has O(n) edges. This way it takes up less space, as well as being faster to traverse.
Some problems are suited for t-spanners (examples are found at this site), while other problems are better solved using other data structures or algorithms. It is a matter of selecting the right tool for the job in hand.
If a problem calls for a t-spanner with certain other properties, algorithms exist for constructing t-spanners with a specified maximum vertex degree.
Then what is this greedy algorithm good for?
The greedy algorithm is intuitive, short and relies on well known principles and algorithms. This makes it relatively easy to understand and to implement. Constructing a spanner of minimum size (minimum collective weight) is a NP-hard problem. Thus, if an approximated version can be used, it is significantly faster to construct than a minimum weight spanner.
In tests comparing it to other t-spanner algorithms it also seems to create sparse graphs. For graphs with n vertices it creates graphs with O(n) edges and a weight close to that of the minimum spanning tree.
This suggest that in actual use, the algorithm yields good results.
At this, and the following, sites you will find applets illustrating the greedy algorithm.
An exercise on the Greedy algorithm is available in the exercises section.