On Resilient Graph Spanners

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

Full description

Saved in:
Bibliographic Details
Published in:Algorithmica 2016-04, Vol.74 (4), p.1363-1385
Main Authors: Ausiello, Giorgio, Franciosa, Paolo G., Italiano, Giuseppe F., Ribichini, Andrea
Format: Article
Language:English
Subjects:
Algorithm Analysis and Problem Complexity
Algorithms
Computer Science
Computer Systems Organization and Communication Networks
Data Structures and Information Theory
Mathematics of Computing
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0178-4617
1432-0541
DOI:10.1007/s00453-015-0006-x