E.: A New Backtracking Algorithm for Constructing Binary Covering Arrays of Variable

Abstract. A Covering Array denoted by CA(N; t, k, v) is a matrix of size N × k, in which each of the vt combinations appears at least once in every t columns. Covering Arrays (CAs) are combinatorial objects used in software testing. There are different methods to construct CAs, but as it is a highly combinatorial problem, few complete algorithms to construct CAs have been reported. In this paper a new backtracking al-gorithm based on the Branch & Bound technique is presented. It searches only non-isomorphic Covering Arrays to reduce the search space of the problem of constructing them. The results obtained with this algorithm are able to match some of the best known solutions for small instances of binary CAs