Chennai Mathematical Institute

Seminars




Spectral Graph Partitioning
Amit Deshpande
MIT, USA.
12-09-07


Abstract

What do eigenvalues and eigenvectors (of Laplacian matrices) reveal about graphs? Can we use them to find good cuts? In this talk, we'll see a result of Spielman-Teng that explains why spectral partitioning techniques perform well in practice. Keywords -- spectral methods, Laplacian matrix, Fiedler vector, planar graphs, Koebe-Andreev-Thurston embedding.