Faster Isomorphism Testing of Strongly Regular Graphs

Author: Daniel A. Spielman.

Bibliographic Information: Appeared in STOC 96: 28th Annual ACM Symposium on Theory of Computing, pages 576-584.


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