TCS / Research / Publications / Isomorph-Free Exhaustive Generation of Combinatorial Designs
Helsinki University of Technology, 
     Laboratory for Theoretical Computer Science

Isomorph-Free Exhaustive Generation of Combinatorial Designs

Reference:

Petteri Kaski. Isomorph-free exhaustive generation of combinatorial designs. Master's thesis, Helsinki University of Technology, Department of Computer Science and Engineering, September 2001.

Abstract:

This thesis investigates algorithmic isomorph-free exhaustive generation of balanced incomplete block designs (BIBDs), resolvable balanced incomplete block designs (RBIBDs), and the corresponding resolutions. In particular, three algorithms for isomorph-free exhaustive generation of -BIBDs and resolutions are described and applied to settle existence and classification problems.

The first algorithm generates BIBDs point by point using an orderly algorithm in combination with a maximum clique algorithm. The second and third algorithm generate resolutions of BIBDs by utilizing a correspondence between resolutions and certain optimal -ary error-correcting codes. The second algorithm generates the corresponding codes codeword by codeword, and is analogous in structure to the first algorithm. The third algorithm generates codes coordinate by coordinate, and is based on the recent isomorph-free exhaustive generation framework of Brendan McKay.

The main result of this thesis is a proof of nonexistence for a (15,5,4) RBIBD by exhaustive computer search. Other new classification results include the classifications of the - and -BIBDs and the -, -, and -RBIBDs together with their resolutions, which correspond to classifications of the , , and error-correcting -codes, respectively. Additionally, a number of earlier classification results are corroborated.

Keywords:

balanced incomplete block design, error-correcting code, exhaustive search, group action, isomorph rejection, orderly algorithm, resolution, resolvable design

Suggested BibTeX entry:

@mastersthesis{Kaski:mscthesis,
    author = {Petteri Kaski},
    month = {September},
    school = {Helsinki University of Technology, Department of Computer Science and Engineering},
    title = {Isomorph-Free Exhaustive Generation of Combinatorial Designs},
    year = {2001},
}

This work is not available online here.

[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 19 January 2010.