Author:
Daniel A. Spielman.
Bibliographic Information:
Appeared in
STOC 96: 28th Annual ACM Symposium on Theory of Computing,
pages 576-584.
Abstract
We demonstrate that isomorphism of strongly regular graphs
may be tested in time $n^{\O{n^{1/3}\log^{2} n}}$.
Our approach is to analyze the standard individualization
and refinement algorithm in light of Neumaier's claw
bound, which implies that low valence strongly regular
graphs have a small second-largest eigenvalue, unless they
are Steiner or Latin square graphs.
You may download the paper in
Daniel A. Spielman
Last modified: Wed Aug 22 16:56:23 2001