On 2-approximation to the vertex-connectivity in graphs

Given a graph G, we give a fast algorithm for approximating the vertex connectivity kappa of G. Our algorithm delivers a minimum vertex cut of G if kappa less than or equal to [delta/2], and returns a message "kappa > [delta/2]" otherwise, where delta denotes the minimum degree of G. The algorithm runs in O(n(2)(1 + min{kappa(2), kappa rootn}/delta)) time and O(n + m) space, where n and m denote the numbers of vertices and edges in G, respectively.