“Computational Methods in Design Theory”

Summary

Introduction

Enumeration theory, which aims to count the number of distinct (non-equivalent) elements in a given class of combinatorial objects, constitutes a significant area in combinatorial analysis. The object of constructive enumeration consists of creating a complete list of configurations with given properties [5,8]. There are several reasons which stimulate research in constructive enumeration. Classical methods are not applicable to many interesting classes of objects such as strongly regular graphs, combinatorial designs, error correcting codes, etc. At present, the only available way to count them is by using algorithmic techniques for fixed values of parameters. Lists of objects are important for generating and testing various hypotheses about invariants, characterization, etc. Moreover, examples of designs with given properties are needed in many areas of applied combinatorics such as coding and experiment planning theories, network reliability and cryptography. Algorithms for constructive enumeration frequently require searching in high dimensional spaces and employ sophisticated techniques to identify partial (final) solutions. Such methods may be of independent interest in artificial intelligence, computer vision, neural networks and combinatorial optimization.

There are several common algorithmic approaches which are used to search for combinatorial configurations with particular properties. These can be divided into two broad classes depending on whether or not they search for all possible solutions in a systematic manner. Among the exhaustive techniques backtracking plays a prominent role. A backtrack algorithm attempts to find a solution vector by recursively building up partial solutions one element at a time. The vectors are examined in lexicographical order until all possible candidates for a component have been exhausted after which one backtracks.