Optimal Offline Dynamic $2,3$-Edge/Vertex Connectivity

Richard Peng, Bryce Sandlund, Daniel D. Sleator

We give offline algorithms for processing a sequence of $2$ and $3$ edge and vertex connectivity queries in a fully-dynamic undirected graph. While the current best fully-dynamic online data structures for $3$-edge and $3$-vertex connectivity require $O(n^{2/3})$ and $O(n)$ time per update, respectively, our per-operation cost is only $O(\log n)$, optimal due to the dynamic connectivity lower bound of Patrascu and Demaine. Our approach utilizes a divide and conquer scheme that transforms a graph into smaller equivalents that preserve connectivity information. This construction of equivalents is closely-related to the development of vertex sparsifiers, and shares important connections to several upcoming results in dynamic graph data structures, outside of just the offline model.

Knowledge Graph



Sign up or login to leave a comment