Spectral Graph Algorithms


Of all the deep connections between combinatorics and linear algebra, those in the field known as spectral graph theory are among the most mysterious. Upon first encounter, it seems quite bizarre that eigenvalues and eigenvectors of matrices should have anything at all to say about graph properties. But when looked at in the right way, this connection turns out to be quite natural and powerful. I have used eigenvectors of the Laplacian matrix in several different application domains including partitioning graphs, organizing databases and assembling gene fragments.


Papers

  • Latent Semantic Analysis and Fiedler Retrieval, Bruce Hendrickson. In Linear Algebra and its Applications, 421:345-355, 2007.
    Paper, Abstract
  • An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations, Bruce Hendrickson and Robert Leland. SIAM J. Sci. Stat. Comput., 16(2):452-469, 1995.
    Paper, Abstract
  • Multidimensional Spectral Load Balancing, Bruce Hendrickson and Robert Leland. In Proc. 6th SIAM Conf. Parallel Proc., 953-961, 1993.
    Paper, Abstract
  • A Spectral Algorithm for Seriation and the Consecutive Ones Problem, Jon E. Atkins, Erik G. Boman and Bruce Hendrickson. SIAM J. Comput. 28(1):297-310, 1998.
    Paper, Abstract

  • Return to Bruce's home page