Speakers: Lucia Moura and Marc Raaphorst
Time:     Tuesday, November 13, at 14:30
Place:    MCD 318 (MacDonald Hall, SITE, University of Ottawa)

Title: Isomorph-free exhaustive generation of some triple systems

Abstract:
We are going to present a general algorithm by Denny and Gibbons (2000)
for exhaustive generation of incidence structures. Their algorithm
consists of several improvements on an algorithm by Gibbons,
Mathon and Corneil (1977).
An incidence structure is a very general combinatorial object:
anything that can be represented as a 0-1 incidence matrix, such as
graphs and hypergraphs. Given v and b, the algorithm produces a
complete list of v by b incidence structures of a certain type
that are distinct up to isomorphism (i.e. up to permutations of rows
and columns). For example, this general framework could be used for
generating all distinct unlabeled graphs with v vertices and b edges
that satisfy your favorite property.
We won't present Denny and Gibbons' algorithm at its full generality,
but will instead show how their framework was applied in an algorithm
designed by us for generating all "maximal anti-Pasch partial Steiner
triple systems" of order up to 15. We will define these "animals",
give some motivation for their study and show that they are equivalent
to certain erasure codes useful for handling failures in large disk
arrays.
Then, we will describe the algorithm we designed for this particular
problem. The larger instances we have solved so far took around 80hs
CPU time on a Sun Blade 1000; this could have taken a lifetime by an
exhaustive search that didn't use permutation groups for rejecting
isomorph duplicates of partial incidence matrices throughout the search.
Hopefully, it will become clear how the same framework can
be applied to other problems. Another nice feature of the algorithm
is that it is fully parallelizable. We are currently working on a new
version of the algorithm in which the search is distributed on a network
of workstations.

( The design and implementation of the sequential algorithm was
  part of the NSERC undergraduate research of Marc under Lucia's
  supervision last summer. The design and implementation of the
  distributed algorithm is part of Marc's undergraduate honours project.)