Electrical Flows and Laplacian Systems: A New Tool for Graph Algorithms

Опубликовано 17 августа 2016, 0:35

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.