Geodesic
Polynomial time recognition and verification of isomorphism of circular graphs
Algebra i analiz, Tome 15 (2003) no. 6, pp. 1-34.

Voir la notice de l'article provenant de la source Math-Net.Ru

@article{AA_2003_15_6_a0,
     author = {S. A. Evdokimov and I. N. Ponomarenko},
     title = {Polynomial time recognition and verification of isomorphism of circular graphs},
     journal = {Algebra i analiz},
     pages = {1--34},
     publisher = {mathdoc},
     volume = {15},
     number = {6},
     year = {2003},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AA_2003_15_6_a0/}
}
TY  - JOUR
AU  - S. A. Evdokimov
AU  - I. N. Ponomarenko
TI  - Polynomial time recognition and verification of isomorphism of circular graphs
JO  - Algebra i analiz
PY  - 2003
SP  - 1
EP  - 34
VL  - 15
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AA_2003_15_6_a0/
LA  - ru
ID  - AA_2003_15_6_a0
ER  - 
%0 Journal Article
%A S. A. Evdokimov
%A I. N. Ponomarenko
%T Polynomial time recognition and verification of isomorphism of circular graphs
%J Algebra i analiz
%D 2003
%P 1-34
%V 15
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AA_2003_15_6_a0/
%G ru
%F AA_2003_15_6_a0
S. A. Evdokimov; I. N. Ponomarenko. Polynomial time recognition and verification of isomorphism of circular graphs. Algebra i analiz, Tome 15 (2003) no. 6, pp. 1-34. http://geodesic.mathdoc.fr/item/AA_2003_15_6_a0/

[1] Babai L., Luks E. M., “Canonical labeling of graphs”, Annual ACM Symposium on Theory of Computing, Proc. 15th Annual ACM Symposium on Theory of Computing, ACM Press, New York, NY, 1983, 171–183

[2] Birkhoff G., Lattice theory, Amer. Math. Soc. Colloq. Publ., 25, Amer. Math. Soc., Providence, RI, 1967 | MR | Zbl

[3] Brouwer A. E., Cohen A. M., Neumaier A., Distance-regular graphs, Ergeb. Math. Grenzgeb. (3), 18, Springer-Verlag, Berlin–New York, 1989 | MR | Zbl

[4] Dixon J. D., Mortimer B., Permutation groups, Grad. Texts in Math., 163, Springer-Verlag, New York, 1996 | MR | Zbl

[5] Evdokimov S., Muzychuk M. E., Ponomarenko I., Tinhofer G., Recognizing certain Cayley graphs in polynomial time, predlozheno v Electron. J. Combin.

[6] Evdokimov S. A., Ponomarenko I. N., “Dva neravenstva dlya parametrov kletochnoi algebry”, Zap. nauch. semin. POMI, 240, 1997, 82–95 | MR | Zbl

[7] Evdokimov S., Ponomarenko I., “Isomorphism of coloured graphs with slowly increasing multiplicity of Jordan blocks”, Combinatorica, 19 (1999), 321–333 | DOI | MR | Zbl

[8] Evdokimov S., Karpinski M., Ponomarenko I., “On a new hlgh-dlmenslonal Welsfeiler–Leman algorithm”, J. Algebraic Combin., 10 (1999), 29–45 | DOI | MR | Zbl

[9] Evdokimov S., Ponomarenko I., “Separability number and schurity number of coherent configurations”, Electron. J. Combin., 7:1 (2000), Res. Paper 31 | MR

[10] Evdokimov S. A., Ponomarenko I. N., “Ob odnom semeistve kolets Shura nad konechnoi tsiklicheskoi gruppoi”, Algebra i analiz, 13:3 (2001), 139–154 | MR

[11] Evdokimov S. A., Ponomarenko I. N., “Kharakterizatsiya tsiklotomicheskikh skhem i normalnye koltsa Shura nad tsiklicheskoi gruppoi”, Algebra i analiz, 14:2 (2002), 11–55 | MR | Zbl

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

[13] Leung K. H., Man S. H., “On Schur rings over cyclic groups. II”, J. Algebra, 183 (1996), 273–285 | DOI | MR | Zbl

[14] Li C. H., “On isomorphisms of finite Cayley graphs – a survey”, Discrete Math., 256 (2002), 301–334 | DOI | MR | Zbl

[15] Lubiw A., “Some NP-complete problems similar to graph isomorphism”, SIAM J. Comput., 10 (1981), 11–21 | DOI | MR | Zbl

[16] Luks E. M., “Permutation groups and polynomial-time computation”, Groups and Computation (New Brunswick, NJ, 1991), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 11, Amer. Math. Soc., Providence, RI, 1993, 139–175 | MR | Zbl

[17] Muzychuk M. E., “On the structure of basic sets of Schur rings over cyclic groups”, J. Algebra, 169 (1994), 655–678 | DOI | MR | Zbl

[18] Muzychuk M., “Ádáms conjecture is true in the square-free case”, J. Combin. Theory Ser. A, 72 (1995), 118–134 | DOI | MR | Zbl

[19] Muzychuk M., “On the isomorphism problem for cyclic combinatorial objects”, Discrete Math., 197/198 (1999), 589–606 | MR | Zbl

[20] Muzychuk M., Klin M., Poschel R., “The isomorphism problem for circulant graphs via Schur ring theory”, Codes and Association Schemes (Piscataway, NJ, 1999), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 56, Amer. Math. Soc., Providence, RI, 2001, 241–264 | MR | Zbl

[21] Muzychuk M. E., Tinhofer G., “Recognizing circulant graphs of prime order in polynomial time”, Electron. J. Combin., 5:1 (1998), Res. Paper 25 | MR

[22] Muzychuk M. E., Tinhofer G., “Recognizing circulant graphs in polynomial time: an application of association schemes”, Electron. J. Combin., 8:1 (2001), Res. Paper 26 | MR | Zbl

[23] Palfy P. P., “A polynomial bound for the orders of primitive solvable groups”, J. Algebra, 77 (1982), 127–137 | DOI | MR | Zbl

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

[25] Schur I., “Zür Theorie der einfach transitiven Permutationsgruppen”, S.-B. Preuss. Akad. Wiss. Phys.-Math. Kl., 18/20 (1933), 598–623 | Zbl

[26] Veisfeiler B. Yu., Leman A. A., “Privedenie grafa k kanonicheskomu vidu i voznikayuschaya pri etom algebra”, Nauchno-tekhn. inform. Sb. VINITI. Ser. 2, 9, 1968, 12–16

[27] Weisfeiler B. (ed.), On the construction and identification of graphs, Lecture Notes in Math., 558, Springer-Verlag, Berlin etc., 1976 | MR | Zbl

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

[29] Wielandt H., Permutation groups through invariant relations and invariant functions, Lecture Notes Dept. Math., Ohio State Univ., Columbus, Ohio, 1969