Computing Vertex Connectivity: New Bounds from Old Techniques
The vertex connectivity K of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. We present the fastest known deterministic algorithm for finding the vertex connectivity and a corresponding separator. The time for a digraph having n vertices and m edges is O(min[pow(K,3) + n, K.n].m) for an undirected graph the term m can be replaced by Kn. A randomized algorithm finds K with error probability 1/2 in time O(nm). If the vertices have nonnegative weights the weighted vertex connectivity is found in time O(K_1.n.m.log(pow2(n)/m)) where K1 m n is the unweighted vertex connectivity or in expected time O(n.m.log(pow2(n)/m)) with error probability 1/2. The main algorithm combines two previous vertex connectivity algorithms and a generalization of the preflow-push algorithm of Hao and Orlin (1994, J. Algorithms 17, 424-446) that computes edge connectivity.
HenzingerRG00.pdf
openaccess
198.33 KB
Adobe PDF
cd6ae3f071743034eaaba48d85ca97f5