Parallel algorithms for the enumeration of combinatorial objects

Submission note: A thesis submitted in total fulfilment of the requirements for the degree of Doctor of Philosophy to the School of Engineering and Mathematical, Faculty of Science, Technology and Engineering, La Trobe University, Bundoora.

The enumeration of combinatorial objects (ECO) plays an important role in combinatorial algorithms. Many scientific applications have used the results from typical servants of ECO, such as maximal clique enumeration, hexagonal system enumeration and the enumeration of orthogonal arrays. The major characteristic of ECO is the huge effort needed to complete the concerned computation. Therefore, parallel approaches for solving ECO could significantly reduce the execution time and generate new results using high performance computing systems. Unfortunately, efficient parallel approaches for ECO are still missing. Researchers in this field usually concentrate on variants of isomorphism techniques for different kinds of combinatorial objects and for parallel computing, they usually use a special batch tool called auto-son [3] to distribute computing across clusters of networks. However, autoson does not provide a parallel environment that allows processes to communicate, such as the Message Passing Interface (MPI) [4], rather it only executes them and waits for them to finish. As a result, little work has been done to discover parallel approaches for ECO. This thesis investigates a number of parallel computing approaches for exhaustive computational search techniques for the construction of combinatorial designs, in particular orthogonal arrays and Latin squares. Several proposed parallel approaches have been designed, implemented and tested for the enumeration of combinatorial objects in general, and for the enumeration of orthogonal arrays and the enumeration of Latin squares, in particular. This thesis: i) proposes a new parallel approach for the enumeration of combinatorial objects based on the OrderlyGeneration method; ii) develops an efficient parallel approach for the enumeration of orthogonal arrays; iii) clarifies the equivalent relationship between a Latin square and its orthogonal representatives in both aspects, theory and experimentation, and iv) proposes a GPU solution for the isomorphism rejection problem where significant findings related to the benefits and challenges of applying GPU computing to the isomorphism rejection problem was made.