On the Complexity of Canonical Labeling of Strongly Regular Graphs

We prove that a canonical labeling can be assigned to the n vertices of a strongly regular graph by an algorithm of o(exp (2n1/2 log ² n)) running time (in the worst case). This complexity, though still not properly subexponential, is much better than O(2ⁿ ).