# Faster Randomized Worst-Case Update Time for Dynamic Subgraph Connectivity

arXiv: https://arxiv.org/abs/1611.09072 · HTML: https://mlsanity.com/paper/1611.09072/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Nov 2016.

## Built on by (most cited first, 1 of 1)

- [Connectivity Oracles for Predictable Vertex Failures](https://mlsanity.com/paper/2312.08489/) (2023)

## Abstract (arXiv)

Real-world networks are prone to breakdowns. Typically in the underlying graph G, besides the insertion or deletion of edges, the set of active vertices changes overtime. A vertex might work actively, or it might fail, and gets isolated temporarily. The active vertices are grouped as a set S. S is subjected to updates, i.e., a failed vertex restarts, or an active vertex fails, and gets deleted from S. Dynamic subgraph connectivity answers the queries on connectivity between any two active vertices in the subgraph of G induced by S. The problem is solved by a dynamic data structure, which supports the updates and answers the connectivity queries. In the general undirected graph, the best results for it include widetildeO(m2/3) deterministic amortized update time, widetildeO(m4/5) and widetildeO(√mn) deterministic worst-case update time. In the paper, we propose a randomized data structure, which has widetildeO(m3/4) worst-case update time.