Sparse Fault-Tolerant BFS Trees

Merav Parter, David Peleg

This paper addresses the problem of designing a sparse {\em fault-tolerant} BFS tree, or {\em FT-BFS tree} for short, namely, a sparse subgraph $T$ of the given network $G$ such th…