Georgia Institute of Technology College of Sciences

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.