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(fn). 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 Õ(fm) 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(mlog3 n) time a sensitivity oracle of size O(mlog2 n), that reports in O(k2 log2 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.

Multiple-edge-fault-tolerant approximate shortest-path trees / Bilò, Davide; Gualà, Luciano; Leucci, Stefano; Proietti, Guido. - 47:(2016). ((Intervento presentato al convegno 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016 tenutosi a fra nel 2016 [10.4230/LIPIcs.STACS.2016.18].

Multiple-edge-fault-tolerant approximate shortest-path trees

BILÒ, Davide;
2016

Abstract

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(fn). 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 Õ(fm) 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(mlog3 n) time a sensitivity oracle of size O(mlog2 n), that reports in O(k2 log2 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.
9783959770019
9783959770019
Multiple-edge-fault-tolerant approximate shortest-path trees / Bilò, Davide; Gualà, Luciano; Leucci, Stefano; Proietti, Guido. - 47:(2016). ((Intervento presentato al convegno 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016 tenutosi a fra nel 2016 [10.4230/LIPIcs.STACS.2016.18].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11388/170898
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 20
  • ???jsp.display-item.citation.isi??? 2
social impact