2016/01/16 by Bilò, Davide, Gualà, Luciano, Leucci, Stefano +1 · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #G.2.2
paper · doi:10.48550/arxiv.1601.04169
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) σ\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 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 \widetildeO(f m) time, has size O(fn log2 n), and is able to report, after the failure of the edge set F, in O(|F|2 log2 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 log3 n) time a sensitivity oracle of size O(m log2 n), that reports in O(k2 log2 n) time the (at most 2k) edges either exiting from or entering into the MSF. [...]