Distributed constructions of dual-failure fault-tolerant distance preservers

DOI10.4230/LIPICS.DISC.2020.21MaRDI QIDQ6535019zbMATHFDO

Authors M. Parter

Publication date 2 November 2023

zbMATH Keywords

fault toleranceCONGESTdistance preservers

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed algorithms (68W15)

Recommendations

• Preserving distances in very faulty graphs
• Fault-tolerant spanners
• Fault tolerant additive and \((\mu, \alpha)\)-spanners
• Fault tolerant additive spanners
• Fault-tolerant spanners for general graphs

Cites work

• A near-linear-time algorithm for computing replacement paths in planar directed graphs
• Chernoff–Hoeffding Bounds for Applications with Limited Independence
• Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles
• Distributed Computing: A Locality-Sensitive Approach
• Distributed algorithms for ultrasparse spanners and linear size skeletons
• Dual failure resilient BFS structure
• Fault tolerant additive and \((\mu, \alpha)\)-spanners
• Finding the most vital node of a shortest path.
• Improved purely additive fault-tolerant spanners
• Multiple source dual fault tolerant BFS trees
• Near optimal algorithms for the single source replacement paths problem
• Near-additive spanners in low polynomial deterministic CONGEST time
• Near-optimal scheduling of distributed algorithms
• Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps
• Preserving distances in very faulty graphs
• Replacement paths and \(k\) simple shortest paths in unweighted directed graphs
• Replacement paths and distance sensitivity oracles via fast matrix multiplication
• Sparse Fault-Tolerant BFS Structures

Cited in

(2)

• Designing distrance-preserving fault-tolerant topologies
• Near-optimal distributed computation of small vertex cuts

This page was built for publication: Distributed constructions of dual-failure fault-tolerant distance preservers

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