Compact and fast sensitivity oracles for single-source distances

DOI10.4230/LIPICS.ESA.2016.13zbMATH Open1397.68135arXiv1608.04769OpenAlexW2521011271MaRDI QIDQ4606282FDOQ4606282

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

Publication date: 2 March 2018

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.

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

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

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)

Cited In (9)

• Efficient Oracles and Routing Schemes for Replacement Paths
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fault-tolerant approximate shortest-path trees
• Deterministic Fault-Tolerant Connectivity Labeling Scheme
• \(f\)-sensitivity distance oracles and routing schemes
• Incremental distance products via faulty shortest paths
• Multiple-edge-fault-tolerant approximate shortest-path trees
• An efficient strongly connected components algorithm in the fault tolerant model

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)