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.

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.