Geodesic
Finding the automorphism group of a circulant association scheme in polynomial time
Zapiski Nauchnykh Seminarov POMI, Problems in the theory of representations of algebras and groups. Part 12, Tome 321 (2005), pp. 251-267 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

We construct a polynomial-time algorithm for finding the automorphism group of a circulant association scheme. The correctness of the algorithm is based on a new result generalizing the Burnside–Schur theorem (on permutation groups having a regular cyclic subgroup) in the class of the automorphism groups of association schemes. 
@article{ZNSL_2005_321_a13,
     author = {I. N. Ponomarenko},
     title = {Finding the automorphism group of a~circulant association scheme in polynomial time},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {251--267},
     year = {2005},
     volume = {321},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2005_321_a13/}
}
TY  - JOUR
AU  - I. N. Ponomarenko
TI  - Finding the automorphism group of a circulant association scheme in polynomial time
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2005
SP  - 251
EP  - 267
VL  - 321
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2005_321_a13/
LA  - ru
ID  - ZNSL_2005_321_a13
ER  - 
%0 Journal Article
%A I. N. Ponomarenko
%T Finding the automorphism group of a circulant association scheme in polynomial time
%J Zapiski Nauchnykh Seminarov POMI
%D 2005
%P 251-267
%V 321
%U http://geodesic.mathdoc.fr/item/ZNSL_2005_321_a13/
%G ru
%F ZNSL_2005_321_a13
I. N. Ponomarenko. Finding the automorphism group of a circulant association scheme in polynomial time. Zapiski Nauchnykh Seminarov POMI, Problems in the theory of representations of algebras and groups. Part 12, Tome 321 (2005), pp. 251-267. http://geodesic.mathdoc.fr/item/ZNSL_2005_321_a13/

[1] B. Yu. Veisfeiler, A. A. Leman, “Privedenie grafa k kanonicheskomu vidu i voznikayuschaya pri etom algebra”, NTI, ser. 2, 9 (1968), 12–16

[2] S. Evdokimov, I. Ponomarenko, “Raspoznavanie i proverka izomorfizma tsirkulyantnykh grafov za polinomialnoe vremya”, Algebra i analiz, 15:6 (2003), 1–34 | MR | Zbl

[3] L. Babai, E. M. Luks, “Canonical labeling of graphs”, Proc. 15th ACM STOC, 1983, 171–183

[4] A. E. Brouwer, A. M. Cohen, A. Neumaier, Distance-regular graphs, Springer, Berlin, 1989 | MR

[5] J. D. Dixon, B. Mortimer, Permutation groups, Graduate Texts in Mathematics, 163, Springer-Verlag, New York, 1996 | MR | Zbl

[6] S. Evdokimov, I. Ponomarenko, “Separability number and schurity number of coherent configurations”, Electronic Journal of Combinatorics, 7 (2000), R31 | MR | Zbl

[7] D. G. Higman, “Coherent configurations, 1”, Rend. Mat. Sem. Padova, 44 (1970), 1–25 | MR

[8] M. Klin, M. Muzychuk, R. Pöschel, “The isomorphism problem for circulant graphs via Schur rings theory”, Codes and association schemes, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 56, Amer. Math. Soc., Providence, RI, 2001, 241–264 | MR | Zbl

[9] E. M. Luks, “Permutation groups and polynomial-time computation”, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 11, 1993, 139–175 | MR | Zbl

[10] R. Mathon, “A note on the graph isomorphism counting problem”, Inform. Process. Lett., 8 (1979), 131–132 | DOI | MR | Zbl

[11] M. Muzychuk, “A solution of the isomorphism problem for circulant graphs”, Proc. London Math. Soc., 88 (2004), 1–41 | DOI | MR | Zbl

[12] I. Ponomarenko, “Polynomial-time algorithms for recognizing and isomorphism testing of cyclic tournaments”, Acta Appl. Math., 29 (1992), 139–160 | DOI | MR | Zbl

[13] B. Weisfeiler (ed.), On construction and identification of graphs, Lecture Notes, 558, Springer Lecture Notes, 1976 | MR | Zbl

[14] H. Wielandt, Finite permutation groups, Academic Press, New York-London, 1964 | MR | Zbl