Computing Vertex Connectivity: New Bounds from Old Techniques |
| |
Authors: | Monika R Henzinger Satish Rao Harold N Gabow |
| |
Institution: | Compaq Systems Research, 130 Lytton Ave, Palo Alto, California, 94301, f1;Computer Science Division, Soda Hall, University of California, Berkeley, California, 94720-1776, , f2;Department of Computer Science, University of Colorado at Boulder, Boulder, Colorado, 80309, , f3 |
| |
Abstract: | The vertex connectivity κ 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{κ3 + n, κn}m); for an undirected graph the term m can be replaced by κn. A randomized algorithm finds κ with error probability 1/2 in time O(nm). If the vertices have nonnegative weights the weighted vertex connectivity is found in time O(κ1nmlog(n2/m)) where κ1 ≤ m/n is the unweighted vertex connectivity or in expected time O(nmlog(n2/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. Algorithms17, 424–446) that computes edge connectivity. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|