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

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 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

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

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

Comments: Email Webmaster

© Copyright , American Mathematical Society
Contact Us · Sitemap · Privacy Statement

Connect with us Facebook Twitter Google+ LinkedIn Instagram RSS feeds Blogs YouTube Podcasts Wikipedia