Fault Tolerant Approximate BFS Structures

DOI10.1137/1.9781611973402.80MaRDI QIDQ5384042zbMATH OpenOpenAlexFDO

Authors M. Parter, David Peleg

Publication date 20 June 2019

Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611973402.80

Mathematics Subject Classification ID

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

Recommendations

• Fault-tolerant approximate BFS structures
• Fault tolerant approximate BFS structures with additive stretch
• Sparse Fault-Tolerant BFS Structures
• Sparse fault-tolerant BFS trees
• Fault-tolerant approximate shortest-path trees
• Fault-tolerant approximate shortest-path trees
• Path-fault-tolerant approximate shortest-path trees
• Multiple-edge-fault-tolerant approximate shortest-path trees
• Multiple-edge-fault-tolerant approximate shortest-path trees
• Multiple source dual fault tolerant BFS trees

Cited in

(19)

• Fault-tolerant approximate shortest-path trees
• Output sensitive fault tolerant maximum matching
• Fault tolerant approximate BFS structures with additive stretch
• Dual failure resilient BFS structure
• Sparse fault-tolerant BFS trees
• Efficient oracles and routing schemes for replacement paths
• Connectivity oracles for graphs subject to vertex failures
• Fault-tolerant approximate BFS structures
• Multiple-edge-fault-tolerant approximate shortest-path trees
• scientific article; zbMATH DE number 6850433 (Why is no real title available?)
• Conditional hardness for sensitivity problems
• Sparse Fault-Tolerant BFS Structures
• Multiple source dual fault tolerant BFS trees
• Sparse weight tolerant subgraph for single source shortest path
• New extremal bounds for reachability and strong-connectivity preservers under failures
• New extremal bounds for reachability and strong-connectivity preservers under failures
• Restorable shortest path tiebreaking for edge-faulty graphs
• Fault tolerant max-cut
• Fault-tolerant bounded flow preservers

This page was built for publication: Fault Tolerant Approximate BFS Structures

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