Thumbnail
Access Restriction
Subscribed

Author Gabow, Harold N.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2006
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Expander graphs ♦ Graphs ♦ Vertex connectivity
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 algorithm for finding κ. For a digraph with $\textit{n}$ vertices, $\textit{m}$ edges and connectivity κ the time bound is $\textit{O}((\textit{n}$ + $min{κ^{&frac52;},$ $κn^{¾}})m).$ This improves the previous best bound of $\textit{O}((\textit{n}$ + $min{κ^{3},$ $κ\textit{n}&rcub)\textit{m}).$ For an undirected graph both of these bounds hold with $\textit{m}$ replaced by $κκ\textit{n}.$ Expander graphs are useful for solving the following subproblem that arises in connectivity computation: A known set $\textit{R}$ of vertices contains two large but unknown subsets that are separated by some unknown set $\textit{S}$ of κ vertices; we must find two vertices of $\textit{R}$ that are separated by $\textit{S}.$
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2006-09-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 53
Issue Number 5
Page Count 45
Starting Page 800
Ending Page 844


Open content in new tab

   Open content in new tab
Source: ACM Digital Library