Lecture 1: Low-stretch trees
Nicholas C. Harvey · 2015
The main theme of the workshop is fast algorithms, particularly those that relate to fast solvers for linear systems involving the Laplacian of a graph. In my lectures, I will discuss three key technical ingredients that underlie those solvers. In this rst lecture, I will discuss \low-stretch trees. Given a graph, the goal is to nd a spanning subtree such that, on average, distances in the tree approximate distances in the graph. These trees have many uses, but we will eventually see that they are particularly useful as preconditioners of Laplacian matrices.