Distance sensitivity oracles with subcubic preprocessing time and fast query time

Shortest paths computation is one of the most fundamental problems in computer science. An important variant of the problem is when edges can fail, and one needs to compute shortest paths that avoid a (failing) edge. More formally, given a source node s,...

A distance sensitivity oracle of an n-vertex graph G = (V,E) is a data structure that can report shortest paths when edges of the graph fail. A query (u ∈ V, v ∈ V, S ⊆ E) to this oracle returns a shortest u-to-v path in the graph G^′ = (V,E ∖ S). We ...

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: ...