Graph Patches (Partial Sparsifiers) and their applications to designing cost-effective, expanding networks
- Combinatorics Seminar
- Friday, April 3, 2009 - 15:00 for 1 hour (actually 50 minutes)
- Skiles 255
- Alexandra Kolla – UC Berkeley
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.