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.
On Resilient Graph Spanners / Ausiello, Giorgio; Franciosa, Paolo Giulio; G. F., Italiano; Ribichini, Andrea. - In: ALGORITHMICA. - ISSN 0178-4617. - STAMPA. - 74:4(2016), pp. 1363-1385. [10.1007/s00453-015-0006-x]
On Resilient Graph Spanners
AUSIELLO, Giorgio;FRANCIOSA, Paolo Giulio;RIBICHINI, ANDREA
2016
Abstract
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.File | Dimensione | Formato | |
---|---|---|---|
Ausiello_Resilient-Graph_2015.pdf
solo gestori archivio
Note: https://link.springer.com/content/pdf/10.1007%2Fs00453-015-0006-x.pdf
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
766.97 kB
Formato
Adobe PDF
|
766.97 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.