Combinatorial Aspects of Covering Arrays
Charles J. Colbourn · 2004
Covering arrays generalize orthogonal arrays by requiring that t-tuples be covered, but not requiring that the appearance of t-tuples be balanced. Their uses in screening experiments has found application in software testing, hardware testing, and a variety of fields in which interactions among factors are to be identified. Here a combinatorial view of covering arrays is adopted, encompassing basic bounds, direct constructions, recursive constructions, algorithmic methods, and applications. 1. Mathematical Preliminaries. An orthogonal array OAλ(N; t, k, v) is an N × k array. In every N × t subarray, each t-tuple occurs exactly λ times, where λ = N vt. The parameter t is the strength; k is the number of factors; and v is the number of levels associated with each factor, the order. The requirement that every t-tuple arise exactly λ times can be too restrictive in applications that require only that every t-tuple be covered at least once. We therefore relax the definition to introduce the covering array and mixed-level covering array. A covering arrayCAλ(N; t, k, v) is an N×k array. In every N×t subarray, each t-tuple occurs at least λ times. Then t is the strength of the coverage of interactions, k is the number of components (degree), and v is the number of