Improved distance sensitivity oracles with subcubic preprocessing time

摘要

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∈V and a failed vertex or edge f∈(V∪E), 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 O˜(n2.7233M) preprocessing time and O(1) query time. Moreover, if the input graph is undirected, the preprocessing time can be improved to O˜(n2.6865M). The preprocessing algorithm is randomized with correct probability ≥1−1/nC, for a constant C that can be made arbitrarily large. This improves the previous best DSO with O˜(n2.8729M) preprocessing time and polylog(n) query time [STOC'20].