Improved distance sensitivity oracles with subcubic preprocessing time

DOI10.1016/J.JCSS.2021.08.005zbMATH Open1472.68119arXiv2007.11495OpenAlexW3196355459MaRDI QIDQ2237898FDOQ2237898

Authors: Hanlin Ren 

Publication date: 28 October 2021

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

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.)

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

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

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)

Cites Work

• Powers of tensors and fast matrix multiplication
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• Oracles for Distances Avoiding a Failed Node or Link
• Title not available (Why is that?)
• A nearly optimal oracle for avoiding failed vertices and edges
• A new approach to dynamic all pairs shortest paths
• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• Matching is as easy as matrix inversion
• Fast algorithms for \((\max, \min)\)-matrix multiplication and bottleneck shortest paths
• Replacement paths and distance sensitivity oracles via fast matrix multiplication
• Dual-failure distance and connectivity oracles
• Title not available (Why is that?)
• Tight hardness for shortest cycles and paths in sparse graphs
• Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor
• On the asymptotic complexity of rectangular matrix multiplication
• 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

Cited In (9)

• Approximate distance sensitivity oracles in subquadratic space
• Distance sensitivity oracles with subcubic preprocessing time and fast query time
• Title not available (Why is that?)
• Analysis and Experimental Evaluation of Time-Dependent Distance Oracles
• Improved distance sensitivity oracles via tree partitioning
• Compact distance oracles with large sensitivity and low stretch
• Title not available (Why is that?)
• Approximate distance sensitivity oracles in subquadratic space
• Conditional hardness for sensitivity problems

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)