{O}(k)-robust spanners in one dimension

Kevin A. Buchin, W.J.T. (Tim) Hulshof, Dániel Olah

Onderzoeksoutput: Andere bijdrageOverige bijdrageAcademic

15 Downloads (Pure)


A geometric t-spanner on a set of points in Euclidean space is a graph containing for every pair of points a path of length at most t times the Euclidean distance between the points. Informally, a spanner is O(k)-robust if deleting k vertices only harms O(k) other vertices. We show that on any one-dimensional set of n points, for any ε>0, there exists an O(k)-robust 1-spanner with O(n1+ε) edges. Previously it was only known that O(k)-robust spanners with O(n2) edges exists and that there are point sets on which any O(k)-robust spanner has Ω(nlogn) edges.
Originele taal-2Engels
UitgeverCornell university
Aantal pagina's6
StatusGepubliceerd - 2018


Duik in de onderzoeksthema's van '{O}(k)-robust spanners in one dimension'. Samen vormen ze een unieke vingerafdruk.

Citeer dit