2026-07-24T10:09:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12945 2024-03-06T10:51:09Z ddc:004 open_access

Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time Ren, Hanlin Graph theory Failure-prone structures We consider the problem of building Distance Sensitivity Oracles (DSOs). Given a directed graph G = (V, E) with edge weights in {1, 2, … , M}, we need to preprocess it into a data structure, and answer the following queries: given vertices u,v,x ∈ V, output the length of the shortest path from u to v that does not go through x. Our main result is a simple DSO with Õ(n^2.7233 M²) preprocessing time and O(1) query time. Moreover, if the input graph is undirected, the preprocessing time can be improved to Õ(n^2.6865 M²). Our algorithms are randomized with correct probability ≥ 1-1/n^c, for a constant c that can be made arbitrarily large. Previously, there is a DSO with Õ(n^2.8729 M) preprocessing time and polylog(n) query time [Chechik and Cohen, STOC'20]. At the core of our DSO is the following observation from [Bernstein and Karger, STOC'09]: if there is a DSO with preprocessing time P and query time Q, then we can construct a DSO with preprocessing time P+Õ(Mn²)⋅ Q and query time O(1). (Here Õ(⋅) hides polylog(n) factors.) Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hanlin Ren 2020 Is Part Of LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2020.79 urn:nbn:de:0030-drops-129450 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.79 eng https://creativecommons.org/licenses/by/3.0/legalcode