Combinatorial aspects of covering arrays

  • Charles J. Colbourn
Keywords: Covering array, Qualitative independence, transversal cover, Orthogonal array, Transversal design, Perfect hash family, Interaction testing, Group-divisible designs, Heuristic search, Greedy algorithm


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.