Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Tower of Covering Arrays

Published

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 Zv with the property that every N×t subarray covers all members of Ztv 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 C0,C1,...,Ch in which for I{/I)=1,2,...,h the covering array Ci is one unit greater in the number of factors and the strength of the covering array Ci-1; this way, if the covering array C0 is of strength t and has k factors then the covering arrays C1,...,Ch 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 Ch 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 Ch 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

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 April 15, 2024)
Created April 25, 2015, Updated November 10, 2018