Multiple source dual fault tolerant BFS trees

DOI10.4230/LIPICS.ICALP.2017.127MaRDI QIDQ5111459zbMATH OpenOpenAlexFDO

Authors Manoj Gupta, Shahbaz Khan

Publication date 27 May 2020

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

zbMATH Keywords

BFSdata structuresfault-tolerancegraph algorithms

Mathematics Subject Classification ID

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

Abstract: Let $G=(V,E)$ be a graph with $n$ vertices and $m$ edges, with a designated set of $sigma$ sources $SsubseteqV$. The fault tolerant subgraph for any graph problem maintains a sparse subgraph $H$ of $G$, such that for any set $F$ of $k$ failures, the solution for the graph problem on $GsetminusF$ is maintained in $HsetminusF$. We address the problem of maintaining a fault tolerant subgraph for Breath First Search tree (BFS) of the graph from a single source $sinV$ (referred as $k$ FT-BFS) or multiple sources $SsubseteqV$ (referred as $k$ FT-MBFS). The problem of $k$ FT-BFS was first studied by Parter and Peleg [ESA13]. They designed an algorithm to compute FT-BFS subgraph of size $O(n^{3/2})$. Further, they showed how their algorithm can be easily extended to FT-MBFS requiring $O(sigm{a}^{1/2}{n}^{3/2})$ space. They also presented matching lower bounds for these results. The result was later extended to solve dual FT-BFS by Parter [PODC15] requiring $O(n^{5/3})$ space, again with matching lower bounds. However, their result was limited to only edge failures in undirected graphs and involved very complex analysis. Moreover, their solution doesn't seems to be directly extendible for dual FT-MBFS problem. We present a similar algorithm to solve dual FT-BFS problem with a much simpler analysis. Moreover, our algorithm also works for vertex failures and directed graphs, and can be easily extended to handle dual FT-MBFS problem, matching the lower bound of $O(sigm{a}^{1/3}{n}^{5/3})$ space described by Parter [PODC15].The key difference in our approach is a much simpler classification of path interactions which formed the basis of the analysis by Parter [PODC15]. Our dual FT-MBFS structure also seamlessly gives a dual fault tolerant spanner with additive stretch of +2 having size $O(n^{7/8})$.

Recommendations

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

Cited in

(25)

• Graph spanners: a tutorial review
• Multiple-edge-fault-tolerant approximate shortest-path trees
• Output sensitive fault tolerant maximum matching
• Dual failure resilient BFS structure
• Sparse fault-tolerant BFS trees
• Fault-tolerant subgraph for single-source reachability: general and optimal
• Sparse Fault-Tolerant BFS Structures
• Generic single edge fault tolerant exact distance oracle
• Fault tolerant and fully dynamic DFS in undirected graphs: simple yet efficient
• Sparse weight tolerant subgraph for single source shortest path
• Fault tolerant subgraph for single source reachability: generic and optimal
• Fault Tolerant Approximate BFS Structures
• New results on linear size distance preservers
• Blackout-tolerant temporal spanners
• Distributed constructions of dual-failure fault-tolerant distance preservers
• Near-optimal distributed computation of small vertex cuts
• An efficient strongly connected components algorithm in the fault tolerant model
• New extremal bounds for reachability and strong-connectivity preservers under failures
• New fault tolerant subset preservers
• 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
• Restorable shortest path tiebreaking for edge-faulty graphs
• Fault tolerant max-cut
• Connectivity labeling in faulty colored graphs
• Title not available (Why is no real title available?)

This page was built for publication: Multiple source dual fault tolerant BFS trees

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