Distributed constructions of dual-failure fault-tolerant distance preservers

DOI10.4230/LIPICS.DISC.2020.21MaRDI QIDQ6535019zbMATH OpenFDO

Authors M. Parter

Publication date 2 November 2023

Full work available at URL https://doi.org/10.4230/LIPICS.DISC.2020.21

zbMATH Keywords

CONGESTdistance preserversfault tolerance

Mathematics Subject Classification ID

Distance in graphs (05C12) Reliability, testing and fault tolerance of networks and computer systems (68M15) Graph theory (including graph drawing) in computer science (68R10) 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 algorithms for ultrasparse spanners and linear size skeletons
• Distributed Computing: A Locality-Sensitive Approach
• 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

(4)

• Designing distrance-preserving fault-tolerant topologies
• Near-optimal distributed computation of small vertex cuts
• Fault tolerant max-cut
• Connectivity labeling in faulty colored graphs

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)