Steve Guattery's Publications

Support Theory

Laplacian Eigenvalue Bounds

The Path Resistance Method for Bounding the Smallest Nontrivial Eigenvalue of a Laplacian by Stephen Guattery, Tom Leighton, and Gary L. Miller. Combinatorics, Probability, and Computing 8(5), 1999, pp. 441-460. This is the revised version of an extended abstract that originally appeared in the Proceedings of the 8th Annual ACM/SIAM Symposium on Discrete Algorithms (SODA '97). Also appeared as ICASE Report 97-51. Also available in a PDF version.

The SODA '97 version is also available ( PDF version).

Applications of Eigenvalue Bounds

• Estimating Interpolation Error: A Combinatorial Approach, by Stephen Guattery, Gary Miller, and Noel Walkington. In Proceedings of the 10th Annual ACM/SIAM Symposium on Discrete Algorithms (SODA '99). Also available in a PDF version.

• Graph Embedding Techniques for Bounding Condition Numbers of Incomplete Factor Preconditioners ICASE Report 97-47. This extends embedding bound to non-diagonally dominant symmetric matrices. Also available in a PDF version.

Exact Embeddings and Inverses

• Graph Embeddings and Laplacian Eigenvalues by Stephen Guattery and Gary L. Miller. SIAM Journal on Matrix Analysis and Applications, 21(3), 2000. This paper gives an exact relationship between graph embeddings and Laplacian eigenvalues. It contains an explanation of why the bounding methods presented in the paper above are not tight. Also available in a PDF version.

• Graph Embeddings, Symmetric Real Matrices, and Generalized Inverses by Stephen Guattery. ICASE Report 98-34. This paper extends the work on the exact relationship between graph embeddings and Laplacian eigenvalues to all symmetric real matrices by generalizing the definition of a current flow embedding. It also demonstrates that the generalized current flow embedding can be used to construct the generalized inverse of the corresponding matrix. Finally, it shows how to extend these results to Hermitian matrices. Also available in a PDF version.

Spectral Partitioning

On the Quality of Spectral Separators by Stephen Guattery and Gary L. Miller. SIAM Journal on Matrix Analysis and Applications, 19(3), 1998. This is the revised version of an extended abstract that originally appeared in the Proceedings of the 6th Annual ACM/SIAM Symposium on Discrete Algorithms (SODA '95). Also available in a PDF version.

Chromatic Polynomials

Chromatic Equivalence of Generalized Ladder Graphs by Stephen Guattery, Gary Haggard, and Ronald C. Read. To appear in Ars Combinatoria. Also available in a PDF version.

Parallel Graph Algorithms

A Contraction Procedure for Planar Directed Graphs by Stephen Guattery and Gary L. Miller. In Proceedings of the Fourth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '92).}. A more complete exposition is available in my Ph.D. Thesis, Carnegie Mellon University, 1995. Also available in a PDF version.

Back to my home page