Lower bounds on 2-covering arrays by exhaustive search
by
Kari J. Nurmela
Helsinki University of Technology
Coauthors: Patric R. J. Östergård

A 2-covering array is a collection of vectors in a discrete space with the property that, in any two coordinate positions, all combinations of the coordinate values occur at least once. 2-covering arrays are also called 2-surjective arrays, qualitatively 2-independent families, group covering designs or transversal covers. In an optimal 2-covering array the number of vectors is minimized. Constructions for optimal 2-covering arrays are known when the vectors are binary vectors, but in the other cases only upper and lower bounds are known. In this work an exhaustive backtrack search is presented that is used to find new lower bounds on the sizes of optimal 2-covering arrays.

Date received: November 10, 2000