Improved distance sensitivity oracles via tree partitioning

DOI10.1007/978-3-319-62127-2_30MaRDI QIDQ2405296zbMATH OpenOpenAlexFDO

Authors Ran Duan, Tianyi Zhang

Publication date 22 September 2017

Full work available at URL https://arxiv.org/abs/1605.04491

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: 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 $ildeO(mn)$ a distance sensitivity oracle of size $O(n^{2}logn)$ 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 $ildeO(mn)$ preprocessing time. One should notice that space complexity and query time of our novel data structure are asymptotically optimal.

Recommendations

• Improved distance sensitivity oracles with subcubic preprocessing time
• Distance sensitivity oracles with subcubic preprocessing time and fast query time
• Replacement paths and distance sensitivity oracles via fast matrix multiplication
• A nearly optimal oracle for avoiding failed vertices and edges
• Faster replacement paths and distance sensitivity oracles

Cited in

(7)

• Improved distance sensitivity oracles with subcubic preprocessing time
• Distance sensitivity oracles with subcubic preprocessing time and fast query time
• Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time.
• Constructing a distance sensitivity oracle in \(O(n^{2.5794}M)\) time
• Undirected 3-fault replacement path in nearly cubic time
• Fault-tolerant approximate distance oracles with a source set
• Incremental distance products via faulty shortest paths

This page was built for publication: Improved distance sensitivity oracles via tree partitioning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2405296)