06101130

a

06101130 Spielman, Daniel A. Algorithms, graph theory, and the solution of Laplacian linear equations. Czumaj, Artur (ed.) et al., Automata, languages, and programming. 39th international colloquium, ICALP 2012, Warwick, UK, July 9--13, 2012. Proceedings, Part II. Berlin: Springer (ISBN 978-3-642-31584-8/pbk). Lecture Notes in Computer Science 7392, 24-26 (2012). 2012 Berlin: Springer EN

doi:10.1007/978-3-642-31585-5_5

Summary: In this talk, we survey major developments in the design of algorithms for solving Laplacian linear equations, by which we mean systems of linear equations in the Laplacian matrices of graphs and their submatrices. We begin with a few examples of where such equations arise, including the analysis of networks of resistors, the analysis of networks of springs, and the solution of maximum flow problems by interior point methods.