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;LEUCCI, STEFANO;PROIETTI, GUIDO
2016-01-01

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
File in questo prodotto:
File Dimensione Formato  
c52 STACS 2016 multiple failures SPT.pdf

accesso aperto

Tipologia: Documento in Versione Editoriale
Licenza: Creative commons
Dimensione 847.15 kB
Formato Adobe PDF
847.15 kB Adobe PDF Visualizza/Apri

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: https://hdl.handle.net/11697/110765
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 20
  • ???jsp.display-item.citation.isi??? 3
social impact