We introduce and investigate a new notion of resilience in graph spanners. Let (Formula presented.) be a spanner of a weighted graph (Formula presented.). Roughly speaking, we say that (Formula presented.) is resilient if all its point-to-point distances are resilient to edge failures. Namely, whenever any edge in (Formula presented.) fails, then as a consequence of this failure all distances do not degrade in (Formula presented.) substantially more than in (Formula presented.) (i.e., the relative distance increases in (Formula presented.) are very close to those in the underlying graph (Formula presented.) ). In this paper we show that sparse resilient spanners exist, and that they can be computed efficiently.
Ausiello, G., Franciosa, P., Italiano, G., Ribichini, A. (2016). On resilient graph spanners. ALGORITHMICA, 74(4), 1363-1385 [10.1007/s00453-015-0006-x].
On resilient graph spanners
Italiano, GF;
2016-01-01
Abstract
We introduce and investigate a new notion of resilience in graph spanners. Let (Formula presented.) be a spanner of a weighted graph (Formula presented.). Roughly speaking, we say that (Formula presented.) is resilient if all its point-to-point distances are resilient to edge failures. Namely, whenever any edge in (Formula presented.) fails, then as a consequence of this failure all distances do not degrade in (Formula presented.) substantially more than in (Formula presented.) (i.e., the relative distance increases in (Formula presented.) are very close to those in the underlying graph (Formula presented.) ). In this paper we show that sparse resilient spanners exist, and that they can be computed efficiently.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
