Multiple source dual fault tolerant BFS trees

DOI10.4230/LIPICS.ICALP.2017.127zbMATH Open1442.68174arXiv1704.06907OpenAlexW2963228239MaRDI QIDQ5111459FDOQ5111459

Manoj Gupta, Shahbaz Khan

Publication date: 27 May 2020

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})$.

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

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

zbMATH Keywords

BFSdata structuresfault-tolerancegraph algorithms

Mathematics Subject Classification ID

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

Cited In (14)

• Title not available (Why is that?)
• Graph spanners: a tutorial review
• Blackout-tolerant temporal spanners
• New Results on Linear Size Distance Preservers
• Near-optimal distributed computation of small vertex cuts
• Sparse Weight Tolerant Subgraph for Single Source Shortest Path
• Sparse Fault-Tolerant BFS Structures
• Fault Tolerant Approximate BFS Structures
• Title not available (Why is that?)
• Dual failure resilient BFS structure
• Multiple-edge-fault-tolerant approximate shortest-path trees
• Distributed constructions of dual-failure fault-tolerant distance preservers
• An efficient strongly connected components algorithm in the fault tolerant model
• Output sensitive fault tolerant maximum matching

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)