Using expander graphs to find vertex connectivity
Author:
Open Access
- 1 September 2006
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 53 (5) , 800-844
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 n vertices, m edges and connectivity κ the time bound is O (( n + min{κ 5/2; , κ n 3/4; }) m ). This improves the previous best bound of O (( n + min{κ 3 , κ n }) m ). For an undirected graph both of these bounds hold with m replaced by κ n . Expander graphs are useful for solving the following subproblem that arises in connectivity computation: A known set R of vertices contains two large but unknown subsets that are separated by some unknown set S of κ vertices; we must find two vertices of R that are separated by S .Keywords
This publication has 15 references indexed in Scilit:
- Expander graphs and their applicationsBulletin of the American Mathematical Society, 2006
- Undirected ST-connectivity in log-space2005
- Computing Vertex Connectivity: New Bounds from Old TechniquesJournal of Algorithms, 2000
- A Static 2-Approximation Algorithm for Vertex Connectivity and Incremental Approximation Algorithms for Edge and Vertex ConnectivityJournal of Algorithms, 1997
- Clique Partitions, Graph Compression and Speeding-Up AlgorithmsJournal of Computer and System Sciences, 1995
- A linear-time algorithm for finding a sparsek-connected spanning subgraph of ak-connected graphAlgorithmica, 1992
- Ramanujan graphsCombinatorica, 1988
- Eigenvalues and expandersCombinatorica, 1986
- Network Flow and Testing Graph ConnectivitySIAM Journal on Computing, 1975
- An Algorithm for Determining Whether the Connectivity of a Graph is at LeastkSIAM Journal on Computing, 1975