Post #436

Recent applications of expanders to graph algorithms Informally, a graph is expander if the nodes are robustly connected, i.e. removing some edges would not break the connectivity. It has been used a lot to improve the running time of many graph algorithms. In this talk, there is a gentle introduction to expanders and their applications to static, dynamic, iterative, and distributed algorithms on graphs.