| Abstract: | By a tournament is meant an oriented graph any pair of whose vertices is joined by precisely one directed edge; a tournament is cyclic if its automorphism group contains a permutation whose cyclic decomposition consists of a unique cycle containing all vertices. In the present paper we describe an algorithm for recognizing the isomorphism of cyclic tournaments. This algorithm has an arbitrary tournament as input. For this tournament, in polynomial time in the number of its vertices it determines its cyclicity, and when it is cyclic it constructs a canonical form for the tournament and generators of its automorphism group. A procedure which constructs the set of all nonconjugate Hamiltonian permutations for a given permutation group of odd order in polynomial time is of independent interest. The technique of construction of the basic algorithm uses both classical results of the theory of computational complexity with permutation groups and Schur's method of S-rings.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklovaa AN SSSR, Vol. 192, pp. 74–111, 1991. |
