Partitioning sparse matrices with eigenvectors of graphs. (English) Zbl 0711.65034

An algebraic approach for computing vertex separators is described. It is shown that the eigenvalues of the Laplacian matrix can be used to get lower bounds on the size of separators. The authors give a heuristic algorithm for computing vertex separators from the second eigenvector of the Laplacian. The algorithm uses global information about the graph to determine separators. It is pointed out that it is sufficient to compute the eigenvector to low accuracy to get good separators for most problems.
Reviewer: R.P.Tewarson


65F50 Computational methods for sparse matrices
65F05 Direct numerical methods for linear systems and matrix inversion
68R10 Graph theory (including graph drawing) in computer science
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
Full Text: DOI Link