2014 | OriginalPaper | Buchkapitel
Fault-Tolerant Approximate Shortest-Path Trees
verfasst von : Davide Bilò, Luciano Gualà, Stefano Leucci, Guido Proietti
Erschienen in: Algorithms - ESA 2014
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The resiliency of a network is its ability to remain
effectively
functioning also when any of its nodes or links fails. However, to reduce operational and set-up costs, a network should be small in size, and this conflicts with the requirement of being resilient. In this paper we address this trade-off for the prominent case of the
broadcasting
routing scheme, and we build efficient (i.e., sparse and fast)
fault-tolerant approximate shortest-path trees
, for both the edge and vertex
single-failure
case. In particular, for an
n
-vertex non-negatively weighted graph, and for any constant
ε
> 0, we design two structures of size
$O(\frac{n \log n}{\varepsilon^2})$
which guarantee (1 +
ε
)-stretched paths from the selected source also in the presence of an edge/vertex failure. This favorably compares with the currently best known solutions, which are for the edge-failure case of size
O
(
n
) and stretch factor 3, and for the vertex-failure case of size
O
(
n
log
n
) and stretch factor 3. Moreover, we also focus on the unweighted case, and we prove that an ordinary (
α
,
β
)-spanner can be slightly augmented in order to build efficient fault-tolerant approximate
breadth-first-search trees
.