Improved distance sensitivity oracles via tree partitioning

Ran Duan, Tianyi Zhang

We introduce an improved structure of distance sensitivity oracle (DSO). The task is to pre-process a non-negatively weighted graph so that a data structure can quickly answer repl…