Biḷ, Davide ;
Gualà, Luciano ;
Leucci, Stefano ;
Proietti, Guido
MultipleEdgeFaultTolerant Approximate ShortestPath Trees
Abstract
Let G be an nnode and medge positively realweighted undirected graph. For any given integer f >= 1, we study the problem of designing a sparse fedgefaulttolerant (fEFT) sigmaapproximate singlesource shortestpath tree (sigmaASPT), 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 fEFT (2F+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 fEFT singlesource 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 (2F+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)) (nonsimultaneous) updates with a worstcase time per update of o(sqrt{n}). Thus, for relatively short sequences of updates, our oracle should be preferred w.r.t. the bestknown (in a worstcase sense) MSF fullydynamic 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 = {{MultipleEdgeFaultTolerant Approximate ShortestPath Trees}},
booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
pages = {18:118:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770019},
ISSN = {18688969},
year = {2016},
volume = {47},
editor = {Nicolas Ollinger and Heribert Vollmer},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5719},
URN = {urn:nbn:de:0030drops57196},
doi = {10.4230/LIPIcs.STACS.2016.18},
annote = {Keywords: faulttolerant shortestpath tree, distance oracle, minimum spanning tree}
}
2016
Keywords: 

faulttolerant shortestpath tree, distance oracle, minimum spanning tree 
Seminar: 

33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Issue date: 

2016 
Date of publication: 

2016 