Covering Arrays and Related Problems in Hypergraphs

Abstract

Covering arrays are an important class of designs in software testing. These are the relaxation of orthogonal arrays in the sense that all tuples only need to appear at least once. It requires fewer number of runs as compared to the orthogonal array. In this talk, we discuss a generalization known as covering arrays on hypergraphs and the construction method to develop the optimal size mixed covering arrays on several families of hypergraphs. Further, we introduce a new class of designs, namely “High index covering arrays (CAλ)”. It fills the gap in between orthogonal arrays and covering arrays such that all tuples are required to appear at least λ times, where λ is a user-defined parameter. We theoretically study the properties of CAλ, and develop a systematic method to construct such designs with minimum run sizes under different number of factors, number of levels, strength and λ.