CanaDAM 2011
University of Victoria, May 31 - June 3, 2011

Covering Arrays, Generalizations and Software Testing Applications II
Org: Peter Danziger (Ryerson University), Lucia Moura (University of Ottawa) and Brett Stevens (Carleton University)

NEVENA FRANCETIC, University of Toronto
Covering Arrays with Row Limit  [PDF]

\emph{Covering Arrays with Row Limit} (CARLs), a generalization of Covering Arrays, are combinatorial models of test suites, having an extra parameter \emph{weight}, $w$, representing the number of components tested at once. We present the lower bound on the size and recursive constructions for optimal $CARL$s with $w=4$ and strength $t=2$ having a regular excess graph. Further search is necessary to find the ingredient $CARL$s for the construction of families whose excess graph is not regular.

BRADY GARVIN, University of Nebraska -- Lincoln
Side Constraints and Covering Array Generation by Simulated Annealing  [PDF]

One technique for generating covering arrays is simulated annealing, which can be seen as a stochastic graph walk where the vertices are given, but we have flexibility in choosing the edges. The edge set affects not only the expected walk length, but also the sensitivity of that expected value to side constraints. We note that both factors affect cost in software testing applications, and we discuss some heuristics for balancing the two objectives.

ANANT GODBOLE, East Tennessee State University
Improving covering array bounds using alternative probability models  [PDF]

Key towards the successful use of probabilistic methods is the right choice of random model, which must be both deep enough to tease out better bounds and simple enough to be tractable. In this talk, I will describe how improvements in upper bounds on the sizes of covering arrays (and partial covering arrays) have been made using equal weight and tiling models. The pros and cons of several other models will be discussed.

SEBASTIAN RAAPHORST, University of Ottawa
Variable Strength Covering Arrays  [PDF]

Variable strength covering arrays (VCA) have their combinations of parameters to cover dictated by the facets of an abstract simplicial complex. We examine a density-based greedy algorithm to find arbitrary VCAs that guarantees that the array size is logarithmically bounded by a function of the number of facets in the simplicial complex when the maximum facet size is bounded by a fixed constant. We also investigate several properties of VCA.

Handling of online submissions has been provided by the CMS.

Event Sponsors

Centre de recherches mathématiques Fields Institute MITACS Pacific Institute for the Mathematical Sciences Canadian Mathematical Society University of Victoria