  The transitive simultaneous conjugacy problem asks whether there exists a
permutation $\tau \in S_n$ such that $b_j = \tau^{-1} a_j \tau$ holds for all
$j = 1,2, \ldots, d$, where $a_1, a_2, \ldots, a_d$ and $b_1, b_2, \ldots, b_d$
are given sequences of $d$ permutations in $S_n$, each of which generates a
transitive subgroup of $S_n$. As from mid 70' it has been known that the
problem can be solved in $O(dn^2)$ time. An algorithm with running time $O(dn
\log(dn))$, proposed in late 80', does not work correctly on all input data. In
this paper we solve the transitive simultaneous conjugacy problem in $O(n^2
\log d / \log n + dn\log n)$ time and $O(n^{3/ 2} + dn)$ space. Experimental
evaluation on random instances shows that the expected running time of our
algorithm is considerably better, perhaps even nearly linear in $n$ at given
$d$.
