Incremental Exact Vertex Connectivity

Felix Adena, Monika Henzinger, Christoph Kern +1

We study the problem of maintaining the vertex connectivity $\kappa$ of a graph under edge insertions. For undirected graphs, our algorithm uses $O({\kappa }^4{\log }^{2}n)$ amortized time per edg…