Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
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 Free Access

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
Email: evdokim@pdmi.ras.ru

I. N. Ponomarenko
Affiliation: St. Petersburg Branch, Steklov Mathematical Institute, Russian Academy of Sciences, Fontanka 27, St. Petersburg 191023, Russia
Email: inp@pdmi.ras.ru

DOI: http://dx.doi.org/10.1090/S1061-0022-04-00833-7
PII: S 1061-0022(04)00833-7
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