### Using expander graphs to find vertex connectivityUsing expander graphs to find vertex connectivity

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

Source: ACM Digital Library