Graph Patches (Partial Sparsifiers) and their applications to designing cost-effective, expanding networks

Series: 
Combinatorics Seminar
Friday, April 3, 2009 - 15:00
1 hour (actually 50 minutes)
Location: 
Skiles 255
,  
UC Berkeley
Organizer: 
I will present an approximation algorithm for the following problem: Given a graph G and a parameter k, find k edges to add to G as to maximize its algebraic connectivity. This problem is known to be NP-hard and prior to this work no algorithm was known with provable approximation guarantee. The algorithm uses a novel way of sparsifying (patching) part of a graph using few edges.