Nearly Linear Time Isomorphism Algorithms for Some Nonabelian Group Classes

The isomorphism problem for groups, when the groups are given by their Cayley tables is a well-studied problem. This problem has been studied for various restricted classes of groups. Kavitha gave a linear time isomorphism algorithm for abelian groups (JCSS 2007). Although there are isomorphism algorithms for certain nonabelian group classes, the complexities of those algorithms are usually super-linear. In this paper, we design linear and nearly linear time isomorphism algorithms for some nonabelian groups. More precisely, We design a linear time algorithm to factor Hamiltonian groups. This allows us to obtain an \(\mathcal {O}(n)\) algorithm for the isomorphism problem of Hamiltonian groups, where n is the order of the groups. We design a nearly linear time algorithm to find a maximal abelian factor of an input group. As a byproduct we obtain an \(\tilde{\mathcal {O}}(n)\) isomorphism for groups that can be decomposed as a direct product of a nonabelian group of bounded order and an abelian group, where n is the order of the groups.