Fault-tolerant approximate BFS structures

DOI10.1145/3022730MaRDI QIDQ4554956zbMATH OpenOpenAlexFDO

Authors M. Parter, David Peleg

Publication date 12 November 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

fault tolerancereplacement pathsadditive spanners

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Abstract: This paper addresses the problem of designing a {em fault-tolerant} $$ approximate BFS structure (or {em FT-ABFS structure} for short), namely, a subgraph $H$ of the network $G$ such that subsequent to the failure of some subset $F$ of edges or vertices, the surviving part of $H$ still contains an emph{approximate} BFS spanning tree for (the surviving part of) $G$, satisfying $$ for every $vinV$. We first consider {em multiplicative} $(alpha,0)$ FT-ABFS structures resilient to a failure of a single edge and present an algorithm that given an $n$-vertex unweighted undirected graph $G$ and a source $s$ constructs a $(3,0)$ FT-ABFS structure rooted at $s$ with at most $4n$ edges (improving by an $O(logn)$ factor on the near-tight result of cite{BS10} for the special case of edge failures). Assuming at most $f$ edge failures, for constant integer $f>1$, we prove that there exists a (poly-time constructible) $(3(f+1),(f+1)logn)$ FT-ABFS structure with $O(fn)$ edges. We then consider {em additive} $$ FT-ABFS structures. In contrast to the linear size of $(alpha,0)$ FT-ABFS structures, we show that for every $$ there exists an $n$-vertex graph $G$ with a source $s$ for which any $$ FT-ABFS structure rooted at $s$ has $$ edges, for some function $$. In particular, $(1,3)$ FT-ABFS structures admit a lower bound of $Omega(n^{5/4})$ edges. Our lower bounds are complemented by an upper bound, showing that there exists a poly-time algorithm that for every $n$-vertex unweighted undirected graph $G$ and source $s$ constructs a $(1,4)$ FT-ABFS structure rooted at $s$ with at most $O(n^{4/3})$ edges.

Recommendations

• Fault Tolerant Approximate BFS Structures
• Fault tolerant approximate BFS structures with additive stretch
• Sparse Fault-Tolerant BFS Structures
• Sparse fault-tolerant BFS trees
• Dual failure resilient BFS structure

Cited in

(14)

• Fault tolerant approximate BFS structures with additive stretch
• Tight bounds on the message complexity of distributed tree verification
• Blackout-tolerant temporal spanners
• Sparse fault-tolerant BFS trees
• Improved purely additive fault-tolerant spanners
• Multiple source dual fault tolerant BFS trees
• Multiple-edge-fault-tolerant approximate shortest-path trees
• Sparse Fault-Tolerant BFS Structures
• Fault Tolerant Approximate BFS Structures
• Dual failure resilient BFS structure
• Path-fault-tolerant approximate shortest-path trees
• Mincut sensitivity data structures for the insertion of an edge
• A nearly linear time construction of approximate single-source distance sensitivity oracles
• Multiple-edge-fault-tolerant approximate shortest-path trees

This page was built for publication: Fault-tolerant approximate BFS structures

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