Fault-Tolerant Subgraph for Single-Source Reachability: General and Optimal

DOI10.1137/16M1087643zbMath1379.05045MaRDI QIDQ4602544

Liam Roditty, Surender Baswana, Keerti Choudhary

Publication date: 31 January 2018

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

reachability; subgraph; fault-tolerant; min-cut

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68W05: Nonnumerical algorithms

05C85: Graph algorithms (graph-theoretic aspects)

05C20: Directed graphs (digraphs), tournaments

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(f\)-sensitivity distance oracles and routing schemes
• Swapping a failing edge of a single source shortest paths tree is good and fast
• Fault tolerant reachability for directed graphs
• Vertex fault tolerant additive spanners
• Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs
• Fault-tolerant compact routing schemes for general graphs
• Dual Failure Resilient BFS Structure
• Sparse Fault-Tolerant BFS Trees
• Fault-Tolerant Approximate Shortest-Path Trees
• Fault-tolerant spanners
• Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems
• Small Stretch Pairwise Spanners and Approximate $D$-Preservers
• Improved Purely Additive Fault-Tolerant Spanners
• Oracles for Distances Avoiding a Failed Node or Link
• A fast algorithm for finding dominators in a flowgraph
• Dynamic DFS in Undirected Graphs: breaking the O(m) barrier
• Better Distance Preservers and Additive Spanners
• Linear Size Distance Preservers
• Strong Connectivity in Directed Graphs under Failures, with Applications
• Fault Tolerant Spanners for General Graphs