Theory Seminar
Using Expander Graphs to Find Vertex Connectivity
Shang-En HuangUniversity of Michigan
WHEN:
Friday, January 29, 2016 @ 10:00 am
Add to Google Calendar
Add to Google Calendar
SHARE:
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.
This work is by Harold N Gabow (2006).