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

Series
Combinatorics Seminar
Time
Friday, April 3, 2009 - 3:00pm for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Alexandra Kolla – UC Berkeley
Organizer
Prasad Tetali
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.