2026-07-22T14:20:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5719 2024-03-06T10:36:55Z ddc:004 open_access

Multiple-Edge-Fault-Tolerant Approximate Shortest-Path Trees Bilò, Davide Gualà, Luciano Leucci, Stefano Proietti, Guido fault-tolerant shortest-path tree distance oracle minimum spanning tree Let G be an n-node and m-edge positively real-weighted undirected graph. For any given integer f >= 1, we study the problem of designing a sparse f-edge-fault-tolerant (f-EFT) sigma-approximate single-source shortest-path tree (sigma-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 sigma. 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 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 single-source distance oracle (SSDO), that can be built in ~{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 minimum spanning forest (MSF) of G after that a 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 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. As a result of independent interest, it is worth noticing that our MSF oracle can be employed to handle arbitrary sequences of o(sqrt[4]{n}/log(n)) (non-simultaneous) updates with a worst-case time per update of o(sqrt{n}). Thus, for relatively short sequences of updates, our oracle should be preferred w.r.t. the best-known (in a worst-case sense) MSF fully-dynamic algorithm, requiring O(sqrt{n}) time per update. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Davide Bilò and Luciano Gualà and Stefano Leucci and Guido Proietti 2016 Is Part Of LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2016.18 urn:nbn:de:0030-drops-57196 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.18 eng https://creativecommons.org/licenses/by/3.0/legalcode