Zhang, Tianyi

Title: SCTL: Improved distance sensitivity oracles via tree partitioning 

Abstract: We introduce an improved structure of distance sensitivity oracle (DSO). The task is to preprocess 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 [Bernstein and Karger, 2009] constructs in time O(mn) a distance sensitivity oracle of size O(n^2 * log(n)) that processes queries in constant time. As an improvement, our oracle takes up O(n^2) space, while preserving constant query efficiency and O(mn) preprocessing time. One should notice that space complexity and query time of our novel data structure are asymptotically optimal.