Fault tolerant approximate BFS structures with additive stretch

DOI10.1007/S00453-020-00734-2MaRDI QIDQ2211352zbMATH OpenOpenAlexFDO

Authors M. Parter, David Peleg

Publication date 11 November 2020

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-020-00734-2

zbMATH Keywords

additive spannersfault tolerancereplacement paths

Mathematics Subject Classification ID

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

Recommendations

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

Cites work

• \(f\)-sensitivity distance oracles and routing schemes
• A nearly optimal algorithm for approximating replacement paths and k shortest simple paths in general graphs
• Additive spanners and \(({\alpha}, {\beta})\)-spanners
• Approximate distance oracles for unweighted graphs in expected \(O(n^2)\) time
• Approximate shortest paths avoiding a failed vertex: optimal size data structures for unweighted graphs
• Constructions of bipartite graphs from finite geometries
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Fault tolerant additive spanners
• Fault Tolerant Approximate BFS Structures
• Fault-tolerant approximate BFS structures
• Fault-tolerant spanners
• Fault-tolerant spanners for general graphs
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• Improved purely additive fault-tolerant spanners
• New additive spanners
• On Pairwise Spanners
• Sparse Fault-Tolerant BFS Structures

Cited in

(7)

• Dual failure resilient BFS structure
• Fault-tolerant approximate BFS structures
• Sparse Fault-Tolerant BFS Structures
• Fault Tolerant Approximate BFS Structures
• Blackout-tolerant temporal spanners
• Restorable shortest path tiebreaking for edge-faulty graphs
• A nearly linear time construction of approximate single-source distance sensitivity oracles

This page was built for publication: Fault tolerant approximate BFS structures with additive stretch

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