Faster Worst-Case Update Time for Dynamic Subgraph Connectivity.
Ran Duan, Le Zhang · arXiv (Cornell University) · 2016
The dynamic subgraph connectivity problem asks how to maintain an understanding of connectivity under vertex updates. An update may switch or off a vertex, and might insert a new edge or delete an existing edge. Queries test the connectivity in the subgraph induced by active ones. Former results on this problem are data structures supporting vertex update in $\widetilde{O}(m^{2/3})$ amortized time, and for worst case the latest result are $\widetilde{O}(m^{4/5})$ and $\widetilde{O}(\sqrt{mn})$. In this paper, we give a structure of linear space, with worst-case update time $\widetilde{O}(m^{3/4})$. The data structure is randomized, as a Monte Carlo dynamic graph algorithm is used as a subroutine.