Graph Paches and Their Applications

SHORT TALKS BY POSTDOCTORAL MEMBERS
Topic:Graph Paches and Their Applications
Speaker:Alexandra Kolla
Affiliation:Member, School of Mathematics
Date:Tuesday, September 29
Time/Room:2:00pm - 3:00pm/S-101

We present a novel way of sparsifying a piece of a graph with very few edges. Our results imply the existence of optimal ultrasparsifiers and efficient approximation algorithms with good approximation guarantee for maximizing the algebraic connectivity of a graph with few edges.