|
|
Please login using the form on menu list.
It is required to login for Full-Text PDF.
|
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.4KB)
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.
|
|
