Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time.

DOI10.4230/LIPICS.ESA.2020.79MaRDI QIDQ5874551zbMATH OpenOpenAlexFDO

Authors Hanlin Ren

Publication date 7 February 2023

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2020/12945/pdf/LIPIcs-ESA-2020-79.pdf/

zbMATH Keywords

failure-prone structuresgraph theory

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A nearly optimal oracle for avoiding failed vertices and edges
• 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
• 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 Cartesian trees and range minimum queries
• 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

(3)

• Distance sensitivity oracles with subcubic preprocessing time and fast query time
• scientific article; zbMATH DE number 7724191 (Why is no real title available?)
• Constructing a distance sensitivity oracle in \(O(n^{2.5794}M)\) time

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