Computing Vertex Connectivity: New Bounds from Old Techniques
✍ Scribed by Monika R. Henzinger; Satish Rao; Harold N. Gabow
- Publisher
- Elsevier Science
- Year
- 2000
- Tongue
- English
- Weight
- 198 KB
- Volume
- 34
- Category
- Article
- ISSN
- 0196-6774
No coin nor oath required. For personal study only.
✦ Synopsis
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 Ž Ä 3 separator. The time for a digraph having n vertices and m edges is O min q 4 . n, n m ; for an undirected graph the term m can be replaced by n. A random-Ž . ized algorithm finds with error probability 1r2 in time O nm . If the vertices have nonnegative weights the weighted vertex connectivity is found in time Ž Ž 2 .. O nmlog n rm where F mrn is the unweighted vertex connectivity or in 1 1 Ž Ž 2 .. expected time O nmlog n rm with error probability 1r2. 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.