Graph isomorphism problem.

This paper is a creative compillation of some recent works on the graph isomorphism problem. An approach to the isomorphism problem due mainly to L. Babai and E. Luks is exposed in the first chapter. This approach which is the most perspective one on our opinion has two specific features: exploiting of some information on the special structure of the automorphism group and profound application of the permutation proup theory to algoritmic aspects of graph isomorphism. In particular, the proofs of the reoognizability of the isomorphism of graphs with bounded valences in polynomial time and of arbitrary graphs in moderately exponential time are given. In the second chapter the Filotty–Mayer–Miller results on the isomorphism of graphs of bounded genus are exposed. The exposition strongly bears our point of view, a number of proofs was altered, the whole demonstration is intended to be more correct and complete than the original one. An algorithm of isomorphism testing for graphs of genus $g$ in time $O(v^{O(g)})$ where v is the number of vertices is described.
In the third chapter some general techniques used in graph isomorphism algorithms are discusesed together with probabilistically estimated and Las Vegas algorithms. In the fourth chapter some other problems related with graph isomorphism are considered.