Fault tolerant subgraph for single source reachability: generic and optimal

DOI10.1145/2897518.2897648zbMath1376.68103OpenAlexW2413699622MaRDI QIDQ5361856

Liam Roditty, Surender Baswana, Keerti Choudhary

Publication date: 29 September 2017

Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2897518.2897648

zbMATH Keywords

fault tolerancesingle-source reachabilityfarthest min-cut

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Related Items (8)

Reachability Preservers: New Extremal Bounds and Approximation Algorithms ⋮ Unnamed Item ⋮ An efficient strongly connected components algorithm in the fault tolerant model ⋮ Approximating the smallest 2-vertex connected spanning subgraph of a directed graph ⋮ Dynamic Dominators and Low-High Orders in DAGs ⋮ Connectivity Oracles for Graphs Subject to Vertex Failures ⋮ Sparse Weight Tolerant Subgraph for Single Source Shortest Path ⋮ Unnamed Item

This page was built for publication: Fault tolerant subgraph for single source reachability: generic and optimal