La Trobe
41901_SOURCE01_1_A.pdf (1.16 MB)

Parallel algorithms for the enumeration of combinatorial objects

Download (1.16 MB)
posted on 2023-01-18, 15:42 authored by Hien H. T. Phan
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.


Center or Department

Faculty of Science, Technology and Engineering. School of Engineering and Mathematical.

Thesis type

  • Ph. D.

Awarding institution

La Trobe University

Year Awarded


Rights Statement

The thesis author retains all proprietary rights (such as copyright and patent rights) over the content of this thesis, and has granted La Trobe University permission to reproduce and communicate this version of the thesis. The author has declared that any third party copyright material contained within the thesis made available here is reproduced and communicated with permission. If you believe that any material has been made available without permission of the copyright owner please contact us with the details.

Data source

arrow migration 2023-01-10 00:15. Ref: latrobe:41901 (9e0739)

Usage metrics

    Open Theses


    No categories selected



    Ref. manager