Steve Guattery's Publications
All files are postscript files unless otherwise noted.
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. 441460.
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
9751. Also available in a
PDF version.
 The
SODA '97 version is also available
(
PDF version).
Applications of Eigenvalue Bounds
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 9834. 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.
Some earlier papers are available at my
page at CMU.
Back to my home page
Last Updated:
Thu Oct 22 17:20:00 1998
send comments about page