The doctoral dissertations of the former Helsinki University of Technology (TKK) and Aalto University Schools of Technology (CHEM, ELEC, ENG, SCI) published in electronic format are available in the electronic publications archive of Aalto University - Aaltodoc.
Aalto

Algorithms for Classification of Combinatorial Objects

Petteri Kaski

Dissertation for the degree of Doctor of Science in Technology to be presented with due permission of the Department of Computer Science and Engineering for public examination and debate in Auditorium T2 at Helsinki University of Technology (Espoo, Finland) on the 15th of June, 2005, at 12 o'clock noon.

Overview in PDF format (ISBN 951-22-7727-1)   [457 KB]
Dissertation is also available in print (ISBN 951-22-7711-5)

Abstract

A recurrently occurring problem in combinatorics is the need to completely characterize a finite set of finite objects implicitly defined by a set of constraints. For example, one could ask for a list of all possible ways to schedule a football tournament for twelve teams: every team is to play against every other team during an eleven-round tournament, such that every team plays exactly one game in every round. Such a characterization is called a classification for the objects of interest. Classification is typically conducted up to a notion of structural equivalence (isomorphism) between the objects. For example, one can view two tournament schedules as having the same structure if one can be obtained from the other by renaming the teams and reordering the rounds.

This thesis examines algorithms for classification of combinatorial objects up to isomorphism. The thesis consists of five articles – each devoted to a specific family of objects – together with a summary surveying related research and emphasizing the underlying common concepts and techniques, such as backtrack search, isomorphism (viewed through group actions), symmetry, isomorph rejection, and computing isomorphism. From an algorithmic viewpoint the focus of the thesis is practical, with interest on algorithms that perform well in practice and yield new classification results; theoretical properties such as the asymptotic resource usage of the algorithms are not considered.

The main result of this thesis is a classification of the Steiner triple systems of order 19. The other results obtained include the nonexistence of a resolvable 2-(15, 5, 4) design, a classification of the one-factorizations of k-regular graphs of order 12 for k ≤ 6 and k = 10, 11, a classification of the near-resolutions of 2-(13, 4, 3) designs together with the associated thirteen-player whist tournaments, and a classification of the Steiner triple systems of order 21 with a nontrivial automorphism group.

This thesis consists of an overview and of the following 5 publications:

  1. P. Kaski and P. R. J. Östergård, 2001. There exists no (15,5,4) RBIBD. Journal of Combinatorial Designs 9, pages 357-362.
  2. P. Kaski and P. R. J. Östergård, 2004. The Steiner triple systems of order 19. Mathematics of Computation 73, pages 2075-2092. © 2004 American Mathematical Society (AMS). By permission.
  3. P. Kaski and P. R. J. Östergård, 2005. One-factorizations of regular graphs of order 12. The Electronic Journal of Combinatorics 12 (1) #R2, 25 pages. © 2005 by authors.
  4. H. Haanpää and P. Kaski, 2005. The near resolvable 2-(13, 4, 3) designs and thirteen-player whist tournaments. Designs, Codes and Cryptography 35, pages 271-285.
  5. P. Kaski, Isomorph-free exhaustive generation of designs with prescribed groups of automorphisms. SIAM Journal on Discrete Mathematics, to appear.

Keywords: classification algorithm, isomorphism, isomorph rejection, near-resolvable design, one-factorization, orderly algorithm, regular graph, resolvable design, Steiner triple system

This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.

© 2005 Helsinki University of Technology

Last update 2011-05-26