Constructing sparse t-spanners with small separators

J. Gudmundsson

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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 languageEnglish
Title of host publicationFundamentals of Computation Theory (Proceedings 14th International Symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003)
EditorsA. Lingas, B.J. Nilsson
Place of PublicationBerlin
PublisherSpringer
Pages86-97
ISBN (Print)3-540-40543-7
DOIs
Publication statusPublished - 2003

Publication series

NameLecture Notes in Computer Science
Volume2751
ISSN (Print)0302-9743

Fingerprint

Dive into the research topics of 'Constructing sparse t-spanners with small separators'. Together they form a unique fingerprint.

Cite this