Tower of Covering Arrays

Published

April 25, 2015

Author(s)

Raghu N. Kacker, Jose Torres Jimenez

Abstract

Covering arrays are combinatorial objects that have several practical applications, specially in the design of experiments for software and hardware testing. A covering array CA(N;t,k,v) of strength t and order v is an N×k array over Z_v with the property that every N×t subarray covers all members of Z^t_v at least once. In this work we explore the construction of a Tower of Covering Arrays (TCA) as a way to produce covering arrays that improve or equal some current upper bounds. A TCA of height h is a succession of h{math plus)1 covering arrays C₀,C₁,...,C_h in which for I{/I)=1,2,...,h the covering array C_i is one unit greater in the number of factors and the strength of the covering array C_i-1; this way, if the covering array C₀ is of strength t and has k factors then the covering arrays C₁,...,C_h are of strength t+1,...,t+h and have {I)k+1,...,k+h factors respectively. We notice that the ratio between the number of rows of the last covering array C_h in a TCA of height h and the number of rows of the best known covering array for the same values of (I}t,k , and v as for C_h is reduced as (I}h{/I) grows. Therefore, we search for TCAs with the greatest height possible. The relevant results are the identification of one infinite TCA for every order {I)v{greater than or equal}2 (even this infinite TCA does not improve any upper bound, and incidentally equivalent results can be obtained using the Zero{/1} - Sum{/1} construction), the improvement of nineteen current upper bounds for v=2 and t {7,8,9,10,11}, and the construction of twenty-one covering arrays that matched current upper bounds. Key

Citation

Discrete Applied Mathematics

Pub Type

Journals

Download Paper

https://doi.org/10.1016/j.dam.2015.03.010

Keywords

covering arrays, tower of covering arrays

Citation

Kacker, R. and Torres, J. (2015), Tower of Covering Arrays, Discrete Applied Mathematics, [online], https://doi.org/10.1016/j.dam.2015.03.010 (Accessed October 31, 2024)