Compact and fast sensitivity oracles for single-source distances

DOI10.4230/LIPICS.ESA.2016.13MaRDI QIDQ4606282zbMATH OpenOpenAlexFDO

Authors D. Bilò, Luciano Gualà, Stefano Leucci, Guido Proietti

Publication date 2 March 2018

Full work available at URL https://arxiv.org/abs/1608.04769

zbMATH Keywords

approximate distancedistance sensitivity oraclefault-tolerant shortest-path tree

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Approximation algorithms (68W25) Distance in graphs (05C12)

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 emph{single-source approximate-distance sensitivity oracles}, namely emph{compact} data structures which are able to emph{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 $Oleft(ncdotfrac1epsilonlogfrac1epsilonight)$, and which is able to report a $(1+epsilon)$-approximate distance from $s$ to any vertex of $G$ in $Oleft(logncdotfrac1epsilonlogfrac1epsilonight)$ 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 emph{additively-stretched} sensitivity oracles, which is helpful to realize the hardness of designing compact oracles of this type.

Recommendations

• \((1 + \epsilon)\)-approximate \(f\)-sensitive distance oracles
• \(f\)-sensitivity distance oracles and routing schemes
• \(f\)-sensitivity distance oracles and routing schemes
• A nearly optimal oracle for avoiding failed vertices and edges
• Replacement paths and distance sensitivity oracles via fast matrix multiplication

Cited in

(11)

• \(f\)-sensitivity distance oracles and routing schemes
• Incremental distance products via faulty shortest paths
• Deterministic Fault-Tolerant Connectivity Labeling Scheme
• Efficient oracles and routing schemes for replacement paths
• An efficient strongly connected components algorithm in the fault tolerant model
• Fault-tolerant approximate shortest-path trees
• Conditional hardness for sensitivity problems
• \((1 + \epsilon)\)-approximate \(f\)-sensitive distance oracles
• Generic single edge fault tolerant exact distance oracle
• \(f\)-sensitivity distance oracles and routing schemes
• Multiple-edge-fault-tolerant approximate shortest-path trees

This page was built for publication: Compact and fast sensitivity oracles for single-source distances

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4606282)