Constructing sparse t-spanners with small separators

J. Gudmundsson

doi:10.1007/978-3-540-45077-1_9

Constructing sparse t-spanners with small separators

J. Gudmundsson

Algorithms

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

1 Citation (Scopus)

Abstract

Given a set of n points TeX in the plane and a real value t>1 we show how to construct in time TeX a t-spanner TeX of TeX such that there exists a set of vertices TeX of size TeX whose removal leaves two disconnected sets TeX and TeX where neither is of size greater than 2/3 · n. The spanner also has some additional properties; low weight and constant degree.

Original language	English
Title of host publication	Fundamentals of Computation Theory (Proceedings 14th International Symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003)
Editors	A. Lingas, B.J. Nilsson
Place of Publication	Berlin
Publisher	Springer
Pages	86-97
ISBN (Print)	3-540-40543-7
DOIs	https://doi.org/10.1007/978-3-540-45077-1_9
Publication status	Published - 2003

Publication series

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

Access to Document

10.1007/978-3-540-45077-1_9

Cite this

@inproceedings{7cb158c1694a429eada0618e2c484f56,

title = "Constructing sparse t-spanners with small separators",

abstract = "Given a set of n points TeX in the plane and a real value t>1 we show how to construct in time TeX a t-spanner TeX of TeX such that there exists a set of vertices TeX of size TeX whose removal leaves two disconnected sets TeX and TeX where neither is of size greater than 2/3 · n. The spanner also has some additional properties; low weight and constant degree.",

author = "J. Gudmundsson",

year = "2003",

doi = "10.1007/978-3-540-45077-1_9",

language = "English",

isbn = "3-540-40543-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "86--97",

editor = "A. Lingas and B.J. Nilsson",

booktitle = "Fundamentals of Computation Theory (Proceedings 14th International Symposium, FCT 2003, Malm{\"o}, Sweden, August 12-15, 2003)",

}

Constructing sparse t-spanners with small separators. / Gudmundsson, J.
Fundamentals of Computation Theory (Proceedings 14th International Symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003). ed. / A. Lingas; B.J. Nilsson. Berlin: Springer, 2003. p. 86-97 (Lecture Notes in Computer Science; Vol. 2751).

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

TY - GEN

T1 - Constructing sparse t-spanners with small separators

AU - Gudmundsson, J.

PY - 2003

Y1 - 2003

N2 - Given a set of n points TeX in the plane and a real value t>1 we show how to construct in time TeX a t-spanner TeX of TeX such that there exists a set of vertices TeX of size TeX whose removal leaves two disconnected sets TeX and TeX where neither is of size greater than 2/3 · n. The spanner also has some additional properties; low weight and constant degree.

AB - Given a set of n points TeX in the plane and a real value t>1 we show how to construct in time TeX a t-spanner TeX of TeX such that there exists a set of vertices TeX of size TeX whose removal leaves two disconnected sets TeX and TeX where neither is of size greater than 2/3 · n. The spanner also has some additional properties; low weight and constant degree.

U2 - 10.1007/978-3-540-45077-1_9

DO - 10.1007/978-3-540-45077-1_9

M3 - Conference contribution

SN - 3-540-40543-7

T3 - Lecture Notes in Computer Science

SP - 86

EP - 97

BT - Fundamentals of Computation Theory (Proceedings 14th International Symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003)

A2 - Lingas, A.

A2 - Nilsson, B.J.

PB - Springer

CY - Berlin

ER -

Constructing sparse t-spanners with small separators

Abstract

Publication series

Access to Document

Fingerprint

Cite this