Algorithms for Distance Sensitivity Oracles and other Graph Problems on the PRAM

Vignesh Manoharan, Vijaya Ramachandran

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 dista…