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) σ-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 O(f m) time, has size O(f n 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( 4 √ n/ log n) (non-simultaneous) updates with a worst-case time per update of o( √ 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( √ n) time per update.
In another result, Bilò et. al. REF designed a k fault tolerant distance oracle of sizeÕ(kn) with a stretch factor of (2k + 1) that can answer queries inÕ(k 2 ) time.
Multiple-Edge-Fault-Tolerant Approximate Shortest-Path Trees
ArXiv
ArXiv
Computer Science Mathematics