Finding Isomorph Classes for Combinatorial Structures

Abstract

A common problem in combinatorial analysis is finding isomorph classes of combinatorial objects. This process is sometimes known as isomorph rejection. In graph theory, it is used to count labelled and unlabelled graphs with certain properties. In chemistry, it is used to count the number of structures with the same chemical formula. In computer science it is used in counting arguments in proofs in complexity theory. In coding theory, it is used to partition sets of vectors into easy to handle sets. This thesis presents three different algorithms for solving this type of problem and compares their timing and memory use. Some examples are given of how to apply the algorithms to graph theory and coding theory.