2026-07-23T22:18:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6364 2024-03-06T10:38:04Z ddc:004 open_access

Compact and Fast Sensitivity Oracles for Single-Source Distances Bilo, Davide Guala, Luciano Leucci, Stefano Proietti, Guido fault-tolerant shortest-path tree approximate distance distance sensitivity oracle 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<epsilon<1, another sensitivity oracle having size O(n*1/epsilon*log(1/epsilon)), and is able to report a (1+epsilon)-approximate distance from s to any vertex of G in O(log(n)*1/epsilon*log(1/epsilon)) 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Davide Bilo and Luciano Guala and Stefano Leucci and Guido Proietti 2016 Is Part Of LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2016.13 urn:nbn:de:0030-drops-63640 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.13 eng https://creativecommons.org/licenses/by/3.0/legalcode