Offline Dynamic Higher Connectivity.
Richard Peng, Bryce Sandlund, Daniel D. Sleator · arXiv (Cornell University) · 2017
We give the first $O(t\log{t})$ time algorithm for processing a given sequence of $t$ edge updates and 3-vertex/edge connectivity queries in an undirected unweighted graph. Our approach builds upon a method by Eppstein (1994) that reduces graphs to smaller equivalents on a set of key vertices. It also leads to algorithms for offline 2-vertex/edge connectivity whose performances match those from Kaczmarz and Lacki (2015).