Speakers:  Lucia Moura and Karen Meagher, University of Ottawa
Time:      Wednesday, July 31, 1:30 p.m.
Place:     room: 5084, SITE (800 King Edward), University of Ottawa
title:     Two generalizations of covering arrays

abstract:
Lucia and Karen will present two short talks which they will present
at the SIAM conference on Discrete Math in August.
The two abstracts are below.

Talk 1: by Lucia Moura (approx 25 min)
"Covering Arrays with Heterogeneous Alphabet Sizes"
Covering arrays are generalizations of orthogonal arrays that have been
used in software and network testing. The vast majority of previous
research has made the simplifying assumption that each row (factor,
parameter) of a covering array has the same alphabet size (number of
levels, parameter values). This assumption is perhaps the most significant
obstacle to the application of the potent mathematical theory of covering
arrays to practical problems.
In this talk, we present a number of constructions for covering arrays
with heterogeneous alphabet sizes. Some are generalizations of
constructions for the homogeneous case, while others take advantage of
differences between alphabet sizes. These results provide a basic
framework for future theoretical and computational research on these
interesting combinatorial objects.
This is joint work with John Stardom, Brett Stevens and Alan Williams.

Talk 2: By Karen Meagher (approx. 25 min)
"Covering arrays on structured networks"
In this paper we extend the definition of 2-covering arrays to include
an underlying graph structure. We then construct covering arrays on
graphs. We know that for any graph there is a covering array at least
as small as the covering array for the chromatic number of the graph.
In this paper we find graphs with covering arrays strictly smaller than
the covering arrays on the chromatic number. We start with focusing on
a binary alphabet and develop a restriction on what graphs can have this
property by constructing a family of graphs. We find a few specific examples.
Finally we consider larger alphabet sizes and find an example for a 6-ary
alphabet. This is a joint work with Brett Stevens.