Home » Publication » 13675

Dettaglio pubblicazione

2016, ALGORITHMICA, Pages 1363-1385 (volume: 74)

On Resilient Graph Spanners (01a Articolo in rivista)

Ausiello Giorgio, Franciosa Paolo Giulio, G. F. Italiano, Ribichini Andrea

We introduce and investigate a new notion of resilience in graph spanners. Let S be a spanner of a weighted graph G. Roughly speaking, we say that S is resilient if all its point- to-point distances are resilient to edge failures. Namely, whenever any edge in G fails, then as a consequence of this failure all distances do not degrade in S substantially more than in G (i.e., the relative distance increases in S are very close to those in the underlying graph G). In this paper we show that sparse resilient spanners exist, and that they can be computed efficiently.
keywords
© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma