Improved distance sensitivity oracles with subcubic preprocessing time

DOI10.1016/J.JCSS.2021.08.005zbMath1472.68119arXiv2007.11495OpenAlexW3196355459MaRDI QIDQ2237898

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

zbMATH Keywords

shortest pathsdistance sensitivity oracles

Mathematics Subject Classification ID

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

Related Items (2)

Compact distance oracles with large sensitivity and low stretch ⋮ Approximate distance sensitivity oracles in subquadratic space

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• Matching is as easy as matrix inversion
• On the asymptotic complexity of rectangular matrix multiplication
• Improved distance sensitivity oracles via tree partitioning
• Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication
• Faster Replacement Paths and Distance Sensitivity Oracles
• 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
• Distance sensitivity oracles with subcubic preprocessing time and fast query time
• A nearly optimal oracle for avoiding failed vertices and edges
• A new approach to dynamic all pairs shortest paths

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