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 ( (2n^1/2 ² n) ) running time (in the worst case). This complexity, though still not properly subexponential, is much better than O (2ⁿ).