multiple edge fault tolerant approximate shortest path trees

• DOI: 10.4230/lipics.stacs.2016.18
• Publication Date: 2021-10-30
• Authors: Bilò, Davide; Gualà, Luciano; Leucci, Stefano; Proietti, Guido
• Keywords: FOS: Computer and information sciences; distance oracle; Distance oracle; Fault-tolerant shortest-path tree; Minimum spanning tree;; Fault-tolerant shortest-path tree; 511; Minimum spanning tree; G.2.2; minimum spanning tree; Settore INF/01 - INFORMATICA; 004; fault-tolerant shortest-path tree; Fully-dynamic minimum spanning tree; Distance sensitivity oracle; Fully-dynamic minimum spanning tree; Multiple-edge fault-tolerant shortest-path tree; Distance oracle; Distance oracle; Fault-tolerant shortest-path tree; Minimum spanning tree; Software; Computer Science - Data Structures and Algorithms; fault-tolerant shortest-path tree, distance oracle, minimum spanning tree; Data Structures and Algorithms (cs.DS); Multiple-edge fault-tolerant shortest-path tree; ddc:004; Distance sensitivity oracle

16 pages, 4 figures<br/>Let $G$ be an $n$-node and $m$-edge positively real-weighted undirected graph. For any given integer $f \ge 1$, we study the problem of designing a sparse \emph{f-edge-fault-tolerant} ($f$-EFT) $��${\em -approximate single-source shortest-path tree} ($��$-ASPT), namely a subgraph of $G$ having as few edges as possible and which, following the failure of a set $F$ of at most $f$ edges in $G$, contains paths from a fixed source that are stretched at most by a factor of $��$. To this respect, we provide an algorithm that efficiently computes an $f$-EFT $(2|F|+1)$-ASPT of size $O(f n)$. Our structure improves on a previous related construction designed for \emph{unweighted} graphs, having the same size but guaranteeing a larger stretch factor of $3(f+1)$, plus an additive term of $(f+1) \log n$. Then, we show how to convert our structure into an efficient $f$-EFT \emph{single-source distance oracle} (SSDO), that can be built in $\widetilde{O}(f m)$ time, has size $O(fn \log^2 n)$, and is able to report, after the failure of the edge set $F$, in $O(|F|^2 \log^2 n)$ time a $(2|F|+1)$-approximate distance from the source to any node, and a corresponding approximate path in the same amount of time plus the path's size. Such an oracle is obtained by handling another fundamental problem, namely that of updating a \emph{minimum spanning forest} (MSF) of $G$ after that a \emph{batch} of $k$ simultaneous edge modifications (i.e., edge insertions, deletions and weight changes) is performed. For this problem, we build in $O(m \log^3 n)$ time a \emph{sensitivity} oracle of size $O(m \log^2 n)$, that reports in $O(k^2 \log^2 n)$ time the (at most $2k$) edges either exiting from or entering into the MSF. [...]<br/>