Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition

Xizhe Li, Yaowei Long, David Pidugu +2

We give an improved connectivity oracle under vertex failures. After a set of $k$ vertices fails, our oracle performs an $O(k^6)$-time update independent of the graph size $n$, a…