Cuts, Trees, and Electrical Flows
Aleksander Madry, EPFL
We discuss some of the recent developments in algorithmic graph theory that are relevant in the context of dealing with massive graphs.
In particular, we present a general framework for obtaining close-to-linear-time approximation algorithms for cut problems in undirected graph. We also introduce the electrical flow paradigm that played key role in some of the recent progress on designing fast algorithms for fundamental flow problems.