Brief Announcement: Algorithms for Distance Sensitivity Oracles on the PRAM

The distance sensitivity oracle (DSO) problem asks us to preprocess a given graph G = (V, E) in order to answer queries of the form d(x, y, e), which denotes the shortest path distance in G from vertex x to vertex y when edge e is removed. This is an important problem for network communication, and it has been extensively studied in the sequential setting [2, 4, 8, 9] and recently in the distributed CONGEST model [7]. However, no prior DSO results tailored to the parallel setting were known. We present the first PRAM algorithms to construct DSOs in directed weighted graphs, that can answer a query in O(1) time with a single processor after preprocessing.