Bryce
Sandlund,
PhD
candidate
David
R.
Cheriton
School
of
Computer
Science
We give offline algorithms 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, including online models.
Joint work with Richard Peng and Daniel D. Sleator.