License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2016.18
URN: urn:nbn:de:0030-drops-57196
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5719/
Bilò, Davide ;
Gualà, Luciano ;
Leucci, Stefano ;
Proietti, Guido
Multiple-Edge-Fault-Tolerant Approximate Shortest-Path Trees
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) 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.
BibTeX - Entry
@InProceedings{bil_et_al:LIPIcs:2016:5719,
author = {Davide Bil{\`o} and Luciano Gual{\`a} and Stefano Leucci and Guido Proietti},
title = {{Multiple-Edge-Fault-Tolerant Approximate Shortest-Path Trees}},
booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
pages = {18:1--18:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-001-9},
ISSN = {1868-8969},
year = {2016},
volume = {47},
editor = {Nicolas Ollinger and Heribert Vollmer},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5719},
URN = {urn:nbn:de:0030-drops-57196},
doi = {10.4230/LIPIcs.STACS.2016.18},
annote = {Keywords: fault-tolerant shortest-path tree, distance oracle, minimum spanning tree}
}
|
Keywords: |
|
fault-tolerant shortest-path tree, distance oracle, minimum spanning tree |
|
Collection: |
|
33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
16.02.2016 |
