Warning: Undefined variable $PHP_SELF in /customers/9/8/1/usmart.dk/httpd.www/bachelor/index.php on line 2 Warning: Undefined array key "id" in /customers/9/8/1/usmart.dk/httpd.www/bachelor/index.php on line 4 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
-
The t-spanner
Introduction
Spanners & t-spanners
t-spanners & MST
The greedy algorithm
The Θ-graph
The applets
Practical application
Exercises
Further reading
Wordlist
  
Contact us
-
-

Introduction

Graphs are mathematical constructs consisting of vertices and edges.

Many computational problems can be expressed as graph problems. For example, planning a route between subway stations translates into finding a path between to vertices of a graph. Another example is planning pipe lines between oil rigs, which corresponds to creating a graph connecting a set of vertices.

Figure 1: Graphs representing real life scenarios
The Copenhagen metro system, expressed as a graph.

Why is this clever?

You may be familiar with algorithms for solving shortest path or minimum spanning tree problems. The benefits of this kind of translation of real-life problems into graph problems include access to a wide range of effective algorithms. Graph representations thus allow for fast and reliable problem solving.

The t-spanner

This site is dedicated the a special kind of graph, namely the t-spanner.
The t-spanner is used to solve problems where a set of vertices need to be connected in such a way, that the shortest path between any two vertices is bounded.

This site will introduces some of the algorithms needed to construct t-spanners, as well as examples of real life problems where the t-spanner is useful.

The t-spanner is primarily used to model geometric objects. For simplicity, this presentation considers vertices to be points in a two dimensional space. The described algorithms do, however, work equally well in other dimensions.

As the graph represents a geometric object, the weight of an edge between two vertices equals the euclidian distance between them.

Navigating this site

The site is divided into 4 subjects:
Supplements include applets illustrating the greedy algorithm and the Θ-graph, exercises, and links to related resources:
  • Applets : Interactive applets and a slide show to illustrate the greedy algorithm and the Θ-graph.

  • Exercises : Test your understanding of t-spanners, the greedy algorithm and the Θ-graph.

  • Further reading : Links to external sources about spanners and their applications.

  • Word list : Short explanations of the terms used in this presentation.


Next -->
Copyright 2005 Anja W-L, Nicolai M.A & Sune H