Seminar Event Detail


Theoretical Computer Science

Date:  Friday, January 29, 2016
Location:  BBB (Room TBA) (10:00 AM to 11:00 AM)

Title:  Using Expander Graphs to Find 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 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).

Files:


Speaker:  Shang-En Huang
Institution:  U-M

Event Organizer:      schoeneb

 

Edit this event (login required).
Add new event (login required).
For access requests and instructions, contact math-webmaster@umich.edu

Back to previous page
Back to UM Math seminars/events page.