2005 | OriginalPaper | Buchkapitel
Experimental Study of Geometric t-Spanners
verfasst von : Mohammad Farshi, Joachim Gudmundsson
Erschienen in: Algorithms – ESA 2005
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The construction of
t
-spanners of a given point set has received a lot of attention, especially from a theoretical perspective. In this paper we perform the first extensive experimental study of the properties of
t
-spanners. The main aim is to examine the quality of the produced spanners in the plane. We implemented the most common
t
-spanner algorithms and tested them on a number of different point sets. The experiments are discussed and compared to the theoretical results and in several cases we suggest modifications that are implemented and evaluated. The quality measurements that we consider are the number of edges, the weight, the maximum degree, the diameter and the number of crossings.