An O ( n 3 log n ) deterministic and an O ( n 3 ) Las Vegs isomorphism test for trivalent graphs
Zvi Galil, Christoph M. Hoffmann, Eugene M. Luks, Claus Peter Schnorr, Andreas Weber⋆ · Journal of the ACM · 1987
This paper describes an O ( n 3 log n ) deterministic algorithm and an O ( n 3 ) Las Vegas algorithm for testing whether two given trivalent graphs on n vertices are isomorphic. In fact, the algorithms construct the set of all isomorphisms between two such graphs, presenting, in particular, generators for the group of all automorphisms of a trivalent graph. The algorithms are based upon the original polynomial-time solution to these problems by Luks but they introduce numerous speedups. These include improved permutation-group algorithms that exploit the structure of the underlying 2-groups. A remarkable property of the Las Vegas algorithm is that it computes the set of all isomorphisms between two trivalent graphs for the cost of computing only those isomorphisms that map a specified edge to a specified edge.