# Fault-Tolerant Approximate Shortest-Path Trees

Preprint · Davide Bilò, Luciano Gualà, Stefano Leucci, Guido Proietti

- Archive id: arxiv:1407.0637
- Published: 2014-07-02
- arXiv: https://arxiv.org/abs/1407.0637
- Source URL: https://arxiv.org/abs/1407.0637
- PDF: https://arxiv.org/pdf/1407.0637
- Provenance: arxiv

## Abstract

The resiliency of a network is its ability to remain \\emph{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 {\\em broadcasting} routing scheme, and we build efficient (i.e., sparse and fast) \\emph{fault-tolerant approximate shortest-path trees}, for both the edge and vertex \\emph{single-failure} case. In particular, for an $n$-vertex non-negatively weighted graph, and for any constant $\\varepsilon \>0$, we design two structures of size $O(\\frac{n \\log n}{\\varepsilon^2})$ which guarantee $(1+\\varepsilon)$-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 \\emph{breadth-first-search trees}.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.