Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Electrical Flows and Laplacian Systems: A New Tool for Graph Algorithms

Speaker  Aleksander Madry

Affiliation  MIT

Host  Yuval Peres

Duration  00:53:45

Date recorded  31 January 2011

In recent years, the emergence of massive computing tasks that arise in context of web applications and networks has made the need for efficient graph algorithms more pressing than ever. In particular, it lead us to focus on reducing the running time of the algorithms to make them as fast as possible, even if it comes at a cost of reducing the quality of the returned solution. This motivates us to expand our algorithmic toolkit to include techniques capable of addressing this new challenge.

In this talk, I will describe how treating a graph as a network of resistors and relating the combinatorial properties of the graph to the electrical properties of the resulting circuit provides us with a powerful new set of tools for the above pursuit. As an illustration of their applicability, I will use these ideas to develop a new technique for approximating the maximum flow in capacitated, undirected graphs that yields the asymptotically fastest-known algorithm for this problem.

©2011 Microsoft Corporation. All rights reserved.
People also watched
> Electrical Flows and Laplacian Systems: A New Tool for Graph Algorithms