Abstract:
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 represented by their Cayley tables, 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.