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 [Bernstein and Karger, 2009] constructs in time ~1O(mn) a distance sensitivity oracle of size O(n~2 log n) that processes queries in O(1) time. As an improvement, our oracle takes up O(n~2) space, while preserving O(1) query efficiency and O(mn) preprocessing time. One should notice that space complexity and query time of our novel data structure are asymptotically optimal.
展开▼
机译：我们介绍了一种改进的距离敏感度预告片（DSO）的结构。任务是对非负加权图进行预处理，以便数据结构可以快速回答源，终端和失败顶点的每三倍的替换路径长度。先前的最佳算法[Bernstein and Karger，2009]在〜10O（mn）的时间内构造了一个大小为O（n〜2 log n）的距离敏感度Oracle，可以在O（1）的时间内处理查询。作为改进，我们的预言机占用了O（n〜2）空间，同时保留了O（1）查询效率和O（mn）预处理时间。应该注意的是，我们新颖的数据结构的空间复杂度和查询时间是渐近最优的。
展开▼
