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

Mikkel Sigurd and Martin Zachariasen
Department of Computer Science, University of Copenhagen

An exact algorithm for constructing minimum-weight spanners in arbitrary graphs, and experimental evaluation of the performance of the greedy algorithm for a set of realistic problem instances.

Mohammad Farshi and Joachim Gudmundsson
Department of Mathematics and computing Science, TU Eindhoven, The Netherlands

The greedy algorithm, the Θ-spanner and other algorithms are tested on sets of points of different size and distribution, and with values of t between 1.05 and 2. The greedy algorithm seems to produces graphs superior to other algorithms in terms of creating sparse spanners with low degree.

Joachim Gudmundsson, Christos Levcopoulos, and Giri Narasimhan
Department of Computer Science, Lund University, Sweeden
Department of Mathematical Sciences, The University of Memphis, USA

A greedy algorithm constructing t-spanners in O(n·log n) time with O(n) edges and weight O(weight(MST)).