Remote Access St. Petersburg Mathematical Journal

St. Petersburg Mathematical Journal

ISSN 1547-7371(online) ISSN 1061-0022(print)



Circulant graphs: recognizing and isomorphism testing in polynomial time

Authors: S. A. Evdokimov and I. N. Ponomarenko
Translated by: the authors
Original publication: Algebra i Analiz, tom 15 (2003), nomer 6.
Journal: St. Petersburg Math. J. 15 (2004), 813-835
MSC (2000): Primary 5C25, 20F65
Published electronically: November 16, 2004
MathSciNet review: 2044629
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: 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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in St. Petersburg Mathematical Journal with MSC (2000): 5C25, 20F65

Retrieve articles in all journals with MSC (2000): 5C25, 20F65

Additional Information

S. A. Evdokimov
Affiliation: St. Petersburg Institute for Informatics and Automation RAS, St. Petersburg, Russia

I. N. Ponomarenko
Affiliation: St. Petersburg Branch, Steklov Mathematical Institute, Russian Academy of Sciences, Fontanka 27, St. Petersburg 191023, Russia

Keywords: Regular cycle automorphism group, Cayley graph, polynomial-time algorithm
Received by editor(s): May 15, 2003
Published electronically: November 16, 2004
Additional Notes: Supported by RFBR (grants nos. 01-01-00219 and 03-01-00349). The second author was supported by RFBR, grants nos. 02-01-00093 and NSh-2251.2003.1.
Article copyright: © Copyright 2004 American Mathematical Society

American Mathematical Society