Sebastian Raaphorst (University of Ottawa)
Variable Strength Covering Arrays

This talk details some of the work completed in my PhD thesis, introducing a generalization of covering arrays where we allow the sets of factors to be covered to be explicitly modelled as a hypergraph. This allows more control over the testing requirements in combinatorial testing using these structures, permitting one to incorporate knowledge of the system under test in the design of the test cases.

We look at several techniques for working with variable strength covering array problems, including divide-and-conquer techniques, hypergraph modifications, generating upper bounds on the sizes of variable strength covering arrays (using a bound derived from a density based greedy algorithm, and another probabilistic based bound that arises from the application of the Lovasz Local Lemma), and we look at several families where the problem of finding minimal size variable strength covering arrays is fully solved.