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

reachabilitysubgraphfault-tolerantmin-cut

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items

Multiple-edge-fault-tolerant approximate shortest-path trees

Cites Work

• 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
• New Pairwise 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
• Multiple-edge-fault-tolerant approximate shortest-path trees
• Fault Tolerant Spanners for General Graphs