Improved distance sensitivity oracles with subcubic preprocessing time

DOI10.1016/J.JCSS.2021.08.005MaRDI QIDQ2237898zbMATH OpenOpenAlexFDO

Authors Hanlin Ren

Publication date 28 October 2021

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2007.11495, https://drops.dagstuhl.de/opus/volltexte/2020/12945/

zbMATH Keywords

shortest pathsdistance sensitivity oracles

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Analysis of algorithms (68W40) Data structures (68P05)

Abstract: We consider the problem of building Distance Sensitivity Oracles (DSOs). Given a directed graph $G=(V,E)$ with edge weights in $1,2,dots,M$, we need to preprocess it into a data structure, and answer the following queries: given vertices $u,vinV$ and a failed vertex or edge $fin(VcupE)$, output the length of the shortest path from $u$ to $v$ that does not go through $f$. Our main result is a simple DSO with $ildeO(n^{2.7233}M)$ preprocessing time and $O(1)$ query time. Moreover, if the input graph is undirected, the preprocessing time can be improved to $ildeO(n^{2.6865}M)$. The preprocessing algorithm is randomized with correct probability $ge1-1/n^C$, for a constant $C$ that can be made arbitrarily large. Previously, there is a DSO with $ildeO(n^{2.8729}M)$ preprocessing time and $operatornamepolylog(n)$ query time [Chechik and Cohen, STOC'20]. At the core of our DSO is the following observation from [Bernstein and Karger, STOC'09]: if there is a DSO with preprocessing time $P$ and query time $Q$, then we can construct a DSO with preprocessing time $P+ildeO(n^2)cdotQ$ and query time $O(1)$. (Here $ildeO(cdot)$ hides $operatornamepolylog(n)$ factors.)

Recommendations

• Distance sensitivity oracles with subcubic preprocessing time and fast query time
• Improved distance sensitivity oracles via tree partitioning
• Faster replacement paths and distance sensitivity oracles
• A nearly optimal oracle for avoiding failed vertices and edges
• Approximate distance oracles with improved preprocessing time

Cites work

• scientific article; zbMATH DE number 5764802 (Why is no real title available?)
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• A nearly optimal oracle for avoiding failed vertices and edges
• A new approach to dynamic all pairs shortest paths
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• Distance sensitivity oracles with subcubic preprocessing time and fast query time
• Dual-failure distance and connectivity oracles
• Fast algorithms for \((\max, \min)\)-matrix multiplication and bottleneck shortest paths
• Faster replacement paths and distance sensitivity oracles
• Improved distance sensitivity oracles via tree partitioning
• Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor
• Matching is as easy as matrix inversion
• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• On the asymptotic complexity of rectangular matrix multiplication
• Oracles for Distances Avoiding a Failed Node or Link
• Powers of tensors and fast matrix multiplication
• Replacement paths and distance sensitivity oracles via fast matrix multiplication
• Tight hardness for shortest cycles and paths in sparse graphs

Cited in

(9)

• Improved distance sensitivity oracles via tree partitioning
• Approximate distance sensitivity oracles in subquadratic space
• Distance sensitivity oracles with subcubic preprocessing time and fast query time
• scientific article; zbMATH DE number 1979527 (Why is no real title available?)
• Compact distance oracles with large sensitivity and low stretch
• Approximate distance sensitivity oracles in subquadratic space
• Conditional hardness for sensitivity problems
• scientific article; zbMATH DE number 7724191 (Why is no real title available?)
• Analysis and Experimental Evaluation of Time-Dependent Distance Oracles

This page was built for publication: Improved distance sensitivity oracles with subcubic preprocessing time

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