Let G be an unweighted n-node undirected graph. A β-additive spanner of G is a spanning subgraph H of G such that distances in H are stretched at most by an additive term β w.r.t. the corresponding distances in G. A natural research goal related with spanners is that of designing sparse spanners with low stretch. In this paper, we focus on fault-tolerant additive spanners, namely additive spanners which are able to preserve their additive stretch even when one edge fails. We are able to improve all known such spanners, in terms of either sparsity or stretch. In particular, we consider the sparsest known spanners with stretch 6, 28, and 38, and reduce the stretch to 4, 10, and 14, respectively (while keeping the same sparsity). Our results are based on two different constructions. On one hand, we show how to augment (by adding a small number of edges) a fault-tolerant additive sourcewise spanner (that approximately preserves distances only from a given set of source nodes) into one such spanner that preserves all pairwise distances. On the other hand, we show how to augment some known fault-tolerant additive spanners, based on clustering techniques. This way we decrease the additive stretch without any asymptotic increase in their size. We also obtain improved fault-tolerant additive spanners for the case of one vertex failure, and for the case of f edge failures.

Improved Purely Additive Fault-Tolerant Spanners / Bilò, Davide; Grandoni, Fabrizio; Gualà, Luciano; Leucci, Stefano; Proietti, Guido. - 9294:(2015), pp. 167-178. (Intervento presentato al convegno 23rd Annual European Symposium on Algorithms tenutosi a Patras (Greece) nel 14-18 September 2015) [10.1007/978-3-662-48350-3_15].

Improved Purely Additive Fault-Tolerant Spanners

BILÒ, Davide;
2015-01-01

Abstract

Let G be an unweighted n-node undirected graph. A β-additive spanner of G is a spanning subgraph H of G such that distances in H are stretched at most by an additive term β w.r.t. the corresponding distances in G. A natural research goal related with spanners is that of designing sparse spanners with low stretch. In this paper, we focus on fault-tolerant additive spanners, namely additive spanners which are able to preserve their additive stretch even when one edge fails. We are able to improve all known such spanners, in terms of either sparsity or stretch. In particular, we consider the sparsest known spanners with stretch 6, 28, and 38, and reduce the stretch to 4, 10, and 14, respectively (while keeping the same sparsity). Our results are based on two different constructions. On one hand, we show how to augment (by adding a small number of edges) a fault-tolerant additive sourcewise spanner (that approximately preserves distances only from a given set of source nodes) into one such spanner that preserves all pairwise distances. On the other hand, we show how to augment some known fault-tolerant additive spanners, based on clustering techniques. This way we decrease the additive stretch without any asymptotic increase in their size. We also obtain improved fault-tolerant additive spanners for the case of one vertex failure, and for the case of f edge failures.
2015
978-3-662-48349-7
Improved Purely Additive Fault-Tolerant Spanners / Bilò, Davide; Grandoni, Fabrizio; Gualà, Luciano; Leucci, Stefano; Proietti, Guido. - 9294:(2015), pp. 167-178. (Intervento presentato al convegno 23rd Annual European Symposium on Algorithms tenutosi a Patras (Greece) nel 14-18 September 2015) [10.1007/978-3-662-48350-3_15].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11388/74657
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 32
  • ???jsp.display-item.citation.isi??? 14
social impact