# Improved distance sensitivity oracles via tree partitioning

arXiv: https://arxiv.org/abs/1605.04491 · HTML: https://mlsanity.com/paper/1605.04491/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 May 2016.

## Built on by (most cited first, 1 of 1)

- [Deep Distance Sensitivity Oracles](https://mlsanity.com/paper/2211.02681/) (2022)

## Abstract (arXiv)

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 replacement path length for every triple of source, terminal and failed vertex. The previous best algorithm constructs in time tildeO(mn) a distance sensitivity oracle of size O(n2log n) that processes queries in O(1) time. As an improvement, our oracle takes up O(n2) space, while preserving O(1) query efficiency and tildeO(mn) preprocessing time. One should notice that space complexity and query time of our novel data structure are asymptotically optimal.