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(pow3(K)+n,K.n)m); for an undirected graph the term m can be replaced by K.n. A randomized algorithm finds K with error probability 1/2 in time O(n.m). If the vertices have nonnegative weights the weighted vertex connectivity is found in time O(K'.n.m.log(pow2(n)/m)) where K' <= m/n is the unweighted vertex connectivity, or in expected time O(nm 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 J. Hao and J.B. [HO] that computes edge connectivity.

Published in:
Proceedings of the 1996 37th Annual Symposium on Foundations of Computer Science, 462-471
Presented at:
Burlington, VT, USA
Other identifiers:
Scopus: 2-s2.0-0030419029

 Record created 2007-01-18, last modified 2018-03-17

Rate this document:

Rate this document:
(Not yet reviewed)