Computing vertex connectivity: New bounds from old techniques

The vertex connectivity kappa of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. We present the fas test known deterministic algorithm for finding the vertex connectivity and a corresponding separator. The time for a digraph having n vertices and m e dges is O(min(kappa(3) + n, kappa n}m); for an undirected graph the term m can be replaced by kappa n. A randomized algorithm finds kappa with error p robability 1/2 in time O(nm). If the vertices have: nonnegative: weights th e weighted vertex connectivity is found in time O(kappa(1)nmlog(n(2)/m)) wh ere kappa(1) less than or equal to m/n is the unweighted vertex connectivit y or in expected time O(nmlog(n(2)/m)) with error probability 1/2. The main algorithm combines two previous vertex connectivity algorithms and a gener alization of the preflow-push algorithm of Hao and Orlin (1994, J. Algorith ms 17, 424-446) that computes edge connectivity. (C) 2000 Academic Press.