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

Pressing the 'add edge' button will enter/exit the edge adding mode. In this mode an edge can be added by first clicking the source and then the target vertex.

The LSP, Longest Shortest Path, button highlights the path (or one of the paths) making up the stretch factor.

Forcing edges to be part of the graph is not a problem using the greedy algorithm. In stead of starting with an empty set of edges, the forced edges are in the set from the beginning.

The reverse, to prevent certain edges from being in the spanner, could be done by assigning the value of ∞ to the distance between the desired veritces. The possible adding of these edges would be considered last by the greedy algorithm, and any path between the two vertices at that time would be short enough.
There are, however, some pitfalls. Primarily it might not be possible to construct a t-spanner with the desired value of t. Another problem would be if all possible edges to a vertex are deemed unwanted, since if none of the edges are added the graph would not be a spanner.