Let s denote a distinguished source vertex of a non-negatively real weighted and undirected graph G with n vertices and m edges. In this paper we present two efficient single-source approximate-distance sensitivity oracles, namely compact data structures which are able to quickly report an approximate (by a multiplicative stretch factor) distance from s to any node of G following the failure of any edge in G. More precisely, we first present a sensitivity oracle of size O(n) which is able to report 2-approximate distances from the source in O(1) time. Then, we further develop our construction by building, for any 0 < ϵ < 1, another sensitivity oracle having size O(n · 1/ϵ log 1/ϵ), and is able to report a (1 + ϵ)-approximate distance from s to any vertex of G in O(log n · 1/ϵ log 1/ϵ) time. Thus, this latter oracle is essentially optimal as far as size and stretch are concerned, and it only asks for a logarithmic query time. Finally, our results are complemented with a space lower bound for the related class of single-source additively-stretched sensitivity oracles, which is helpful to realize the hardness of designing compact oracles of this type.

Compact and fast sensitivity oracles for single-source distances

Bilò, Davide;LEUCCI, STEFANO;PROIETTI, GUIDO
2016-01-01

Abstract

Let s denote a distinguished source vertex of a non-negatively real weighted and undirected graph G with n vertices and m edges. In this paper we present two efficient single-source approximate-distance sensitivity oracles, namely compact data structures which are able to quickly report an approximate (by a multiplicative stretch factor) distance from s to any node of G following the failure of any edge in G. More precisely, we first present a sensitivity oracle of size O(n) which is able to report 2-approximate distances from the source in O(1) time. Then, we further develop our construction by building, for any 0 < ϵ < 1, another sensitivity oracle having size O(n · 1/ϵ log 1/ϵ), and is able to report a (1 + ϵ)-approximate distance from s to any vertex of G in O(log n · 1/ϵ log 1/ϵ) time. Thus, this latter oracle is essentially optimal as far as size and stretch are concerned, and it only asks for a logarithmic query time. Finally, our results are complemented with a space lower bound for the related class of single-source additively-stretched sensitivity oracles, which is helpful to realize the hardness of designing compact oracles of this type.
9783959770156
File in questo prodotto:
File Dimensione Formato  
c54 ESA 2016 oracle single-failure SPT.pdf

accesso aperto

Tipologia: Documento in Versione Editoriale
Licenza: Creative commons
Dimensione 625.48 kB
Formato Adobe PDF
625.48 kB Adobe PDF Visualizza/Apri

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/11697/110763
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? ND
social impact