Circulant graphs: recognizing and isomorphism testing in polynomial time
Sergey A. Evdokimov, Ilia Nikolaevich Ponomarenko · St Petersburg Mathematical Journal · 2004
An algorithm is constructed for recognizing the circulant graphs and finding a canonical labeling for them in polynomial time. This algorithm also yields a cycle base of an arbitrary solvable permutation group. The consistency of the algorithm is based on a new result on the structure of Schur rings over a finite cyclic group.