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.
200 University Avenue West
Waterloo, ON N2L 3G1