Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > BOUNDED VALENCE GRAPHS:
Reports tagged with Bounded Valence Graphs:
TR11-052 | 4th April 2011
Fabian Wagner

#### On the Complexity of Group Isomorphism

The group isomorphism problem consists in deciding whether two groups \$G\$ and \$H\$
given by their multiplication tables are isomorphic.
An algorithm for group isomorphism attributed to Tarjan runs in time \$n^{\log n + O(1)}\$, c.f. [Mil78].

Miller and Monk showed in [Mil79] that group isomorphism can be many-one ... more >>>

ISSN 1433-8092 | Imprint