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

fault tolerancereplacement pathsadditive spanners

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• 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 Approximate BFS Structures
• Fault tolerant additive spanners
• Fault-tolerant approximate BFS structures
• Fault-tolerant spanners
• Fault-tolerant spanners for general graphs
• Improved purely additive fault-tolerant spanners
• New additive spanners
• On Pairwise Spanners
• Sparse Fault-Tolerant BFS Structures
• \(f\)-sensitivity distance oracles and routing schemes

Cited in

(5)

• Blackout-tolerant temporal spanners
• Sparse Fault-Tolerant BFS Structures
• Fault Tolerant Approximate BFS Structures
• Dual failure resilient BFS structure
• Fault-tolerant approximate BFS structures

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)