Abstract
We consider the problem of building Distance Sensitivity Oracles (DSOs). Given a directed graph G = (V, E) with edge weights in {1, 2, … , M}, we need to preprocess it into a data structure, and answer the following queries: given vertices u,v,x ∈ V, output the length of the shortest path from u to v that does not go through x. Our main result is a simple DSO with Õ(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 Õ(n^2.6865 M²). Our algorithms are randomized with correct probability ≥ 11/n^c, for a constant c that can be made arbitrarily large. Previously, there is a DSO with Õ(n^2.8729 M) preprocessing time and polylog(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+Õ(Mn²)⋅ Q and query time O(1). (Here Õ(⋅) hides polylog(n) factors.)
BibTeX  Entry
@InProceedings{ren:LIPIcs:2020:12945,
author = {Hanlin Ren},
title = {{Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
pages = {79:179:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771627},
ISSN = {18688969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12945},
URN = {urn:nbn:de:0030drops129450},
doi = {10.4230/LIPIcs.ESA.2020.79},
annote = {Keywords: Graph theory, Failureprone structures}
}
Keywords: 

Graph theory, Failureprone structures 
Collection: 

28th Annual European Symposium on Algorithms (ESA 2020) 
Issue Date: 

2020 
Date of publication: 

26.08.2020 