Experimental study of geometric t-spanners

M. Farshi; J. Gudmundsson

doi:10.1007/11561071_50

Experimental study of geometric t-spanners

M. Farshi
, J. Gudmundsson

Algorithms

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

17 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	Algorithms - ESA 2005
Subtitle of host publication	13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005. Proceedings
Editors	G.S. Brodal, S. Leonardi
Place of Publication	Berlin
Publisher	Springer
Chapter	50
Pages	556-567
Number of pages	12
ISBN (Electronic)	978-3-540-31951-1
ISBN (Print)	3-540-29118-0, 978-3-540-29118-3
DOIs	https://doi.org/10.1007/11561071_50
Publication status	Published - 2005

Publication series

Name	Lecture Notes in Computer Science
Volume	3669
ISSN (Print)	0302-9743

Access to Document

10.1007/11561071_50

Cite this

@inproceedings{6ca56931beee4125826e9a8a52bef6a2,

title = "Experimental study of geometric t-spanners",

abstract = "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.",

author = "M. Farshi and J. Gudmundsson",

year = "2005",

doi = "10.1007/11561071\_50",

language = "English",

isbn = "3-540-29118-0",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "556--567",

editor = "G.S. Brodal and S. Leonardi",

booktitle = "Algorithms - ESA 2005",

address = "Germany",

}

Experimental study of geometric t-spanners. / Farshi, M.; Gudmundsson, J.
Algorithms - ESA 2005: 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005. Proceedings. ed. / G.S. Brodal; S. Leonardi. Berlin: Springer, 2005. p. 556-567 (Lecture Notes in Computer Science; Vol. 3669).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Experimental study of geometric t-spanners

AU - Farshi, M.

AU - Gudmundsson, J.

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

U2 - 10.1007/11561071_50

DO - 10.1007/11561071_50

M3 - Conference contribution

SN - 3-540-29118-0

SN - 978-3-540-29118-3

T3 - Lecture Notes in Computer Science

SP - 556

EP - 567

BT - Algorithms - ESA 2005

A2 - Brodal, G.S.

A2 - Leonardi, S.

PB - Springer

CY - Berlin

ER -

Experimental study of geometric t-spanners

Abstract

Publication series

Access to Document

Fingerprint

Cite this