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

Explanations of selected terms used in this presentation.

A

B

The Big O notation is a notation used to express an upper bound on the number of computations made, amount of space used, etc., by an algorithm. For more information consult: Wikipedia on Big O notation http://en.wikipedia.org/wiki/Big_O_notation

A Binary search tree is a binary tree with the property that any element stored in any nodesk left subtree
is smaller than k and any alement stored in the right subtree is bigger. In a balanced, binary search tree with n elements the height of the tree, and thus the maximum number of nodes to traverse in a search, is at most O(log n).
For more information consult: Wikipedia on binary search trees http://en.wikipedia.org/wiki/Binary_search_tree

A Binary tree is a tree that is rooted, and in which each node has at most two subtrees.

C

D

The Detour factor of two vertices is the length of a shortest path between them in proportion to their euclidian distance.

Dijkstra, Edsger Wybe. Dutch computer analyst (1930-2002) known not least because of Dijkstras algorithm.

E

The Euclidian distance between two vertices is the direct (as the crow flies) distance between them.

Figure 13: Euclidean distance

The direct geometric distance.
The euclidian distance between p1 and p2 is 1.8 .

F

G

A Graph, G(V, E), is a computational consisting of vertices, V, to some degree connected by edges, E. In this presentation we only consider geometric graphs. This means that the weight of an edge equals the euclidean distance between the vertices it connects.

"A Greedy algorithm always makes the choice that looks best at the moment. That is, it makes a locally optimal choice in the hope that this choice wille lead to a globally optimal solution." Introduction to Algorithms p. 370, T. H. Cormen et al.
For more information consult Wikipedia on greedy algorithms: http://en.wikipedia.org/wiki/Greedy_algorithm

A Longest Shortest Path or LSP of a graph is the path (or one of the paths) making up the stretch factor.

M

A Minimun Spanning Tree (MST) is a set of edges spanning a set of vertices in such a way that the collective weight of the edges is as low as posible.

Merge sort is an algorithm sorting n elements in O(n·log n) time. For more informations consult:
Wikipedia on proteins http://en.wikipedia.org/wiki/Mergesort

Quicksort is an algorithm sorting n elements in O(n·log n) time. For more informations consult:
Wikipedia on proteins http://en.wikipedia.org/wiki/Quicksort

R

S

A Shortest path is the smallest possible length travelled when moving from one vertice to another along the edges of a graph. If it exists, it can be found in O(V·log V + E) time by Dijkstras algorithm.

A Spanner is a network of edges connecting all vertices of a set.

The Stretch Factor of a graph is the largest detour factor of the graph.

T

A t-spanner is a graph, G(E, V), where the shortest path between any two vertices is at most t times their euclidian distance.

A Tree is a conected graph without cykles. The number of edges in a tree is the number of vertices minus one.

U

V

W

This is the word list. Terms used in the presentation are explained and links to external ressources put available.