TCS / Research / Publications / Isomorph-free exhaustive generation of designs with prescribed groups of automorphisms
Helsinki University of Technology, 
     Laboratory for Theoretical Computer Science

Isomorph-free exhaustive generation of designs with prescribed groups of automorphisms

Reference:

Petteri Kaski. Isomorph-free exhaustive generation of designs with prescribed groups of automorphisms. SIAM Journal on Discrete Mathematics, 19(3):664–690, 2005.

Abstract:

We develop an algorithm framework for isomorph-free exhaustive generation of designs admitting a group of automorphisms from a prescribed collection of pairwise non-conjugate groups, where each prescribed group has a large index relative to its normalizer in the isomorphism-inducing group. We demonstrate the practicality of the framework by producing a complete classification of the Steiner triple systems of order 21 admitting a nontrivial automorphism group. The number of pairwise nonisomorphic such designs is 62336617, where 958 of the designs are anti-Pasch. We also develop consistency checking methodology for gaining confidence in the correct operation of the algorithm implementation.

Keywords:

classification algorithm, combinatorial search, consistency checking, isomorph rejection, isomorph-free generation, Kramer-Mesner method, Steiner triple system, symmetry reduction

Suggested BibTeX entry:

@article{Kaski05,
    author = {Petteri Kaski},
    journal = {SIAM Journal on Discrete Mathematics},
    number = {3},
    pages = {664--690},
    title = {Isomorph-free exhaustive generation of designs with prescribed groups of automorphisms},
    volume = {19},
    year = {2005},
}

See dx.doi.org ...

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