CINECA IRIS Institutional Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishLet 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.
Bilo, D., Guala, L., Leucci, S., & Proietti, G. (2016). Compact and fast sensitivity oracles for single-source distances. In 24th Annual European Symposium on Algorithms, ESA 2016. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing [10.4230/LIPIcs.ESA.2016.13].
| Autori: | ||
| Autori: | Bilo, D; Guala, L; Leucci, S; Proietti, G | |
| Titolo: | Compact and fast sensitivity oracles for single-source distances | |
| Nome del convegno: | 24th Annual European Symposium on Algorithms, ESA 2016 | |
| Luogo del convegno: | Aarhus, Denmark | |
| Anno del convegno: | 2016 | |
| Rilevanza: | Rilevanza internazionale | |
| Sezione: | contributo | |
| Data di pubblicazione: | 2016 | |
| Digital Object Identifier (DOI): | http://dx.doi.org/10.4230/LIPIcs.ESA.2016.13 | |
| Settore Scientifico Disciplinare: | Settore INF/01 - Informatica | |
| Lingua: | English | |
| URL: | http://drops.dagstuhl.de/opus/institut_lipics.php?fakultaet=04 | |
| Tipologia: | Intervento a convegno | |
| Citazione: | Bilo, D., Guala, L., Leucci, S., & Proietti, G. (2016). Compact and fast sensitivity oracles for single-source distances. In 24th Annual European Symposium on Algorithms, ESA 2016. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing [10.4230/LIPIcs.ESA.2016.13]. | |
| Appare nelle tipologie: | 02 - Intervento a convegno |
File in questo prodotto:
Copyright © 2022