Faster Randomized Worst-Case Update Time for Dynamic Subgraph Connectivity

Ran Duan, Le Zhang

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 verte…