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