Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time.

DOI10.4230/LIPIcs.ESA.2020.79OpenAlexW3081705060MaRDI QIDQ5874551

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

graph theoryfailure-prone structures

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On Cartesian trees and range minimum queries
• 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
• 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

This page was built for publication: Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time.