Menu
The Graph Isomorphism (GI) problem asks if two graphs are isomorphic. Algorithms which solve GI have applications in, but not limited to, SAT solver engines, isomorph-free generation, combinatorial analysis, and analyzing chemical structures. However, no algorithm has been found which solves GI in polynomial time, implying that hard instances should exist. One of the most popular algorithms, implemented in the software package nauty, canonically labels a graph and outputs generators for its automorphism group. In this paper, we present some methods that improve its performance on graphs that are known to pose difficulty.