δ/2" otherwise, where δ denotes the minimum degree of G. The algorithm runs in O(n2(1 + min {κ2, κ/δ)) time and O(n + m) space, where n and m denote the numbers of vertices and edges in G, respectively." />


On 2-Approximation to the Vertex-Connectivity in Graphs

Hiroshi NAGAMOCHI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E88-D   No.1   pp.12-16
Publication Date: 2005/01/01
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
Category: 
Keyword: 
graph algorithm,  approximation algorithm,  vertex-connectivity,  MA orderings,  minimum degree,  

Full Text: PDF(128.7KB)
>>Buy this Article


Summary: 
Given a graph G, we give a fast algorithm for approximating the vertex connectivity κ of G. Our algorithm delivers a minimum vertex cut of G if κ δ/2, and returns a message "κ > δ/2" otherwise, where δ denotes the minimum degree of G. The algorithm runs in O(n2(1 + min {κ2, κ/δ)) time and O(n + m) space, where n and m denote the numbers of vertices and edges in G, respectively.