On the Complexity of Canonical Labeling of Strongly Regular Graphs
László Babai · SIAM Journal on Computing · 1980
We prove that a canonical labeling can be assigned to the n vertices of a strongly regular graph by an algorithm of $o(\exp (2n^{1/2} \log ^2 n))$ running time (in the worst case). This complexity, though still not properly subexponential, is much better than $O(2^n )$.