2026-07-26T00:07:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14145 2024-03-06T10:53:35Z ddc:004 open_access

Constructing a Distance Sensitivity Oracle in O(n^2.5794 M) Time Gu, Yong Ren, Hanlin graph theory shortest paths distance sensitivity oracles We continue the study of distance sensitivity oracles (DSOs). Given a directed graph G with n vertices and edge weights in {1, 2, … , M}, we want to build a data structure such that given any source vertex u, any target vertex v, and any failure f (which is either a vertex or an edge), it outputs the length of the shortest path from u to v not going through f. Our main result is a DSO with preprocessing time O(n^2.5794 M) and constant query time. Previously, the best preprocessing time of DSOs for directed graphs is O(n^2.7233 M), and even in the easier case of undirected graphs, the best preprocessing time is O(n^2.6865 M) [Ren, ESA 2020]. One drawback of our DSOs, though, is that it only supports distance queries but not path queries. Our main technical ingredient is an algorithm that computes the inverse of a degree-d polynomial matrix (i.e. a matrix whose entries are degree-d univariate polynomials) modulo x^r. The algorithm is adapted from [Zhou, Labahn and Storjohann, Journal of Complexity, 2015], and we replace some of its intermediate steps with faster rectangular matrix multiplication algorithms. We also show how to compute unique shortest paths in a directed graph with edge weights in {1, 2, … , M}, in O(n^2.5286 M) time. This algorithm is crucial in the preprocessing algorithm of our DSO. Our solution improves the O(n^2.6865 M) time bound in [Ren, ESA 2020], and matches the current best time bound for computing all-pairs shortest paths. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yong Gu and Hanlin Ren 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.76 urn:nbn:de:0030-drops-141450 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.76 eng https://creativecommons.org/licenses/by/4.0/legalcode