Sparse fault-tolerant BFS trees

DOI10.1007/978-3-642-40450-4_66MaRDI QIDQ2849365zbMATH OpenOpenAlexFDO

Authors M. Parter, David Peleg

Publication date 17 September 2013

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1302.5401

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Reliability, testing and fault tolerance of networks and computer systems (68M15) Graph theory (including graph drawing) in computer science (68R10)

Abstract: 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 that subsequent to the failure of a single edge or vertex, the surviving part $T^{\prime }$ of $T$ still contains a BFS spanning tree for (the surviving part of) $G$. Our main results are as follows. We present an algorithm that for every $n$-vertex graph $G$ and source node $s$ constructs a (single edge failure) FT-BFS tree rooted at $s$ with $O(ncdotminDepth(s),sqrtn)$ edges, where $Depth(s)$ is the depth of the BFS tree rooted at $s$. This result is complemented by a matching lower bound, showing that there exist $n$-vertex graphs with a source node $s$ for which any edge (or vertex) FT-BFS tree rooted at $s$ has $Omega(n^{3/2})$ edges. We then consider {em fault-tolerant multi-source BFS trees}, or {em FT-MBFS trees} for short, aiming to provide (following a failure) a BFS tree rooted at each source $sinS$ for some subset of sources $SsubseteqV$. Again, tight bounds are provided, showing that there exists a poly-time algorithm that for every $n$-vertex graph and source set $SsubseteqV$ of size $sigma$ constructs a (single failure) FT-MBFS tree $T^{\ast }(S)$ from each source $s_{i}inS$, with $O(sqrtsigmacdot{n}^{3/2})$ edges, and on the other hand there exist $n$-vertex graphs with source sets $SsubseteqV$ of cardinality $sigma$, on which any FT-MBFS tree from $S$ has $Omega(sqrtsigmacdot{n}^{3/2})$ edges. Finally, we propose an $O(logn)$ approximation algorithm for constructing FT-BFS and FT-MBFS structures. The latter is complemented by a hardness result stating that there exists no $Omega(logn)$ approximation algorithm for these problems under standard complexity assumptions.

Recommendations

• Sparse Fault-Tolerant BFS Structures
• Dual failure resilient BFS structure
• Fault Tolerant Approximate BFS Structures
• Fault-tolerant approximate BFS structures
• Multiple source dual fault tolerant BFS trees

Cited in

(31)

• Unsafe operations in B-trees
• Fault-tolerant approximate shortest-path trees
• Graph spanners: a tutorial review
• Multiple-edge-fault-tolerant approximate shortest-path trees
• Output sensitive fault tolerant maximum matching
• Fault tolerant approximate BFS structures with additive stretch
• Dual failure resilient BFS structure
• Fault-tolerant approximate shortest-path trees
• Efficient oracles and routing schemes for replacement paths
• Connectivity oracles for graphs subject to vertex failures
• Improved purely additive fault-tolerant spanners
• Fault tolerance and storage reduction in binary search trees
• Fault-tolerant approximate BFS structures
• Multiple-edge-fault-tolerant approximate shortest-path trees
• Fault-tolerant subgraph for single-source reachability: general and optimal
• scientific article; zbMATH DE number 913359 (Why is no real title available?)
• Sparse Fault-Tolerant BFS Structures
• Generic single edge fault tolerant exact distance oracle
• Multiple source dual fault tolerant BFS trees
• Sparse weight tolerant subgraph for single source shortest path
• Fault Tolerant Approximate BFS Structures
• New results on linear size distance preservers
• Reachability Preservers: New Extremal Bounds and Approximation Algorithms
• An efficient strongly connected components algorithm in the fault tolerant model
• New extremal bounds for reachability and strong-connectivity preservers under failures
• New extremal bounds for reachability and strong-connectivity preservers under failures
• Near optimal algorithm for fault tolerant distance oracle and single source replacement path problem
• Near optimal dual fault tolerant distance oracle
• Connectivity labeling in faulty colored graphs
• Fault-tolerant bounded flow preservers
• A deterministic approach to shortest path restoration in edge faulty graphs

This page was built for publication: Sparse fault-tolerant BFS trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2849365)