Deterministic Fault-Tolerant Connectivity Oracles with Subqadratic SpaceResearch Paper
A fault-tolerant connectivity oracle preprocesses a graph once and then answers questions about for failure sets of edges that arrive later: are two vertices still connected, or what are the connected components? Such oracles are studied as data structures, as labeling schemes, and as one-way communication protocols, and the central resource is the s…