Steklov Institute of Mathematics at St.Petersburg

PREPRINT 03/2003

RECOGNIZING AND ISOMORPHISM TESTING CIRCULANT GRAPHS IN POLYNOMIAL TIME

This preprint was accepted May 12, 2003
Contact: Ilia Ponomarenko

ABSTRACT:
We recognize the circulant graphs and find canonical labeling for them in
polynomial time. As a part, the algorithm includes finding a cycle base of an
arbitrary solvable permutation group. The correctness of the algorithm
is based on a new result on the structure of Schur rings over a finite
cyclic group.