We introduce and investigate a new notion of resilience in graph spanners. Let S be a spanner of a graph G. Roughly speaking, we say that a spanner 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. © 2013 Springer-Verlag.
On resilient graph spanners / Ausiello, Giorgio; Franciosa, Paolo Giulio; Giuseppe Francesco, Italiano; Ribichini, Andrea. - STAMPA. - 8125 LNCS:(2013), pp. 85-96. (Intervento presentato al convegno 21st Annual European Symposium on Algorithms, ESA 2013 tenutosi a Sophia Antipolis nel 2 September 2013 through 4 September 2013) [10.1007/978-3-642-40450-4_8].
On resilient graph spanners
AUSIELLO, Giorgio;FRANCIOSA, Paolo Giulio;RIBICHINI, ANDREA
2013
Abstract
We introduce and investigate a new notion of resilience in graph spanners. Let S be a spanner of a graph G. Roughly speaking, we say that a spanner 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. © 2013 Springer-Verlag.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
