Constructions of covering arrays of strength five

A covering array of size N, strength t, degree k and order v, or a CA(N; t, k, v) in short, is an N × k array on v symbols. In every N × t subarray, each t-tuple occurs in at least one row. Covering arrays have been studied for their significant applications to generating software test suites to cover all t-sets of component interactions. In this paper, we present two constructive methods to obtain covering arrays of strength 5 by using difference covering arrays and holey difference matrices with a prescribed property. As a consequence, some new upper bounds on the covering numbers are derived.     

Roux-type constructions for covering arrays of strengths three and four

A covering array CA(N;t,k,v) is an N × k array such that every N × t sub-array contains all t-tuples from v symbols at least once, where t is the strength of the array. Covering arrays are used to generate software test suites to cover all t-sets of component interactions. Recursive constructions for covering arrays of strengths 3 and 4 are developed, generalizing many “Roux-type” constructions. A numerical comparison with current construction techniques is given through existence tables for covering arrays.      

Products of mixed covering arrays of strength two

A covering array CA(N;t,k, v is an N × k array such that every N × t subarray contains all t‐tuples from v symbols at least once, where t is the strength of the array. Covering arrays are used to generate software test suites to cover all t‐sets of component interactions. The particular case when t = 2 (pairwise coverage) has been extensively studied, both to develop combinatorial constructions and to provide effective algorithmic search techniques. In this paper, a simple “cut‐and‐paste” construction is extended to covering arrays in which different columns (factors) admit different numbers of symbols (values); in the process an improved recursive construction for covering arrays with t = 2 is derived. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 124–138, 2006     

Covering arrays of strength 3 and 4 from holey difference matrices

A covering array CA(N; t, k, v) is an N × k array with entries from a set X of v symbols such that every N × t sub-array contains all t-tuples over X at least once, where t is the strength of the array. The minimum size N for which a CA(N; t, k, v) exists is called the covering array number and denoted by CAN(t, k, v). Covering arrays are used in experiments to screen for interactions among t-subsets of k components. One of the main problems on covering arrays is to construct a CA(N; t, k, v) for given parameters (t, k, v) so that N is as small as possible. In this paper, we present some constructions of covering arrays of strengths 3 and 4 via holey difference matrices with prescribed properties. As a consequence, some of known bounds on covering array number are improved. In particular, it is proved that (1) CAN(3, 5, 2v) ≤ 2v ²(4v + 1) for any odd positive integer v with gcd(v, 9) ≠ 3; (2) CAN(3, 6, 6p) ≤ 216p ³ + 42p ² for any prime p > 5; and (3) CAN(4, 6, 2p) ≤ 16p ⁴ + 5p ³ for any prime p ≡ 1 (mod 4) greater than 5.     

On the state of strength‐three covering arrays

A covering array of size N, strength t, degree k, and order υ is a k × N array on υ symbols in which every t × N subarray contains every possible t × 1 column at least once. We present explicit constructions, constructive upper bounds on the size of various covering arrays, and compare our results with those of a commercial product. Applications of covering arrays include software testing, drug screening, and data compression. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 217–238, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10002     

Covering arrays of higher strength from permutation vectors

A covering array CA(N;t,k,v) is an N × k array such that every N × t sub‐array contains all t‐tuples from v symbols at least once, where t is the strength of the array. Covering arrays are used to generate software test suites to cover all t‐sets of component interactions. We introduce a combinatorial technique for their construction, focussing on covering arrays of strength 3 and 4. With a computer search, covering arrays with improved parameters have been found. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 202–213, 2006     

Constructions of new orthogonal arrays and covering arrays of strength three

A covering array of size N, strength t, degree k, and order v, or a CA(N;t,k,v) in short, is a k×N array on v symbols. In every t×N subarray, each t-tuple column vector occurs at least once. When ‘at least’ is replaced by ‘exactly’, this defines an orthogonal array, OA(t,k,v). A difference covering array, or a DCA(k,n;v), over an abelian group G of order v is a k×n array (aij) (1?i?k, 1?j?n) with entries from G, such that, for any two distinct rows l and h of D (1?l<h?k), the difference list Δlh={dh1−dl1,dh2−dl2,…,dhn−dln} contains every element of G at least once.Covering arrays have important applications in statistics and computer science, as well as in drug screening. In this paper, we present two constructive methods to obtain orthogonal arrays and covering arrays of strength 3 by using DCAs. As a consequence, it is proved that there are an OA(3,5,v) for any integer v?4 and v?2 (mod 4), and an OA(3,6,v) for any positive integer v satisfying gcd(v,4)≠2 and gcd(v,18)≠3. It is also proved that the size CAN(3,k,v) of a CA(N;3,k,v) cannot exceed v³+v² when k=5 and v≡2 (mod 4), or k=6, v≡2 (mod 4) and gcd(v,18)≠3.     

Constructing strength three covering arrays with augmented annealing

A covering arrayCA(N;t,k,v) is an N×k array such that every N×t sub-array contains all t-tuples from v symbols at least once, where t is the strength of the array. One application of these objects is to generate software test suites to cover all t-sets of component interactions. Methods for construction of covering arrays for software testing have focused on two main areas. The first is finding new algebraic and combinatorial constructions that produce smaller covering arrays. The second is refining computational search algorithms to find smaller covering arrays more quickly. In this paper, we examine some new cut-and-paste techniques for strength three covering arrays that combine recursive combinatorial constructions with computational search; when simulated annealing is the base method, this is augmented annealing. This method leverages the computational efficiency and optimality of size obtained through combinatorial constructions while benefiting from the generality of a heuristic search. We present a few examples of specific constructions and provide new bounds for some strength three covering arrays.     

Group construction of covering arrays

A covering array t‐CA (n, k, g) is a k × n array on a set of g symbols with the property that in each t × n subarray, every t × 1 column appears at least once. This paper improves many of the best known upper bounds on n for covering arrays, 2‐CA (n, k, g) with g + 1 ≤ k ≤ 2g, for g = 3 · · · 12 by a construction which in many of these cases produces a 2‐CA (n, k, g) with n = k (g ? 1) + 1. The construction is an extension of an algebraic method used by Chateauneuf, Colbourn, and Kreher which uses an array and a group action on the array. © 2004 Wiley Periodicals, Inc. J Combin Designs 13: 70–77, 2005.     

On the structure of small strength‐2 covering arrays

A covering array $\text{CA}\left(N;t,k,v\right)$ of strength $t$ is an $N\times k$ array of symbols from an alphabet of size $v$ such that in every $N\times t$ subarray, every $t$‐tuple occurs in at least one row. A covering array is optimal if it has the smallest possible $N$ for given $t$, $k$, and $v$, and uniform if every symbol occurs $?N∕v?$ or $?N∕v?$ times in every column. Before this paper, the only known optimal covering arrays for $t=2$ were orthogonal arrays, covering arrays with $v=2$ constructed from Sperner's Theorem and the Erd?s‐Ko‐Rado Theorem, and 11 other parameter sets with $v>2$ and $N>v^2$. In all these cases, there is a uniform covering array with the optimal size. It has been conjectured that there exists a uniform covering array of optimal size for all parameters. In this paper, a new lower bound as well as structural constraints for small uniform strength‐2 covering arrays is given. Moreover, covering arrays with small parameters are studied computationally. The size of an optimal strength‐2 covering array with $v>2$ and $N>v^2$ is now known for 21 parameter sets. Our constructive results continue to support the conjecture.     

Explicit constructions for perfect hash families

Let k, v, t be integers such that k ≥ v ≥ t ≥ 2. A perfect hash family (N; k, v, t) can be defined as an N × k array with entries from a set of v symbols such that every N × t subarray contains at least one row having distinct symbols. Perfect hash families have been studied by over 20 years and they find a wide range of applications in computer sciences and in cryptography. In this paper we focus on explicit constructions for perfect hash families using combinatorial methods. We present many recursive constructions which result in a large number of improved parameters for perfect hash families. The paper also includes extensive tables for parameters with t = 3, 4, 5, 6 of newly constructed perfect hash families.      

Mixed covering arrays on graphs

Covering arrays have applications in software, network and circuit testing. In this article, we consider a generalization of covering arrays that allows mixed alphabet sizes as well as a graph structure that specifies the pairwise interactions that need to be tested. Let k and n be positive integers, and let G be a graph with k vertices v₁,v₂,…, v_k with respective vertex weights g₁ ≤ g₂ ≤ … ≤ g_k. A mixed covering array on G, denoted by , is an n × k array such that column i corresponds to v_i, cells in column i are filled with elements from ?_gi and every pair of columns i,j corresponding to an edge v_i,v_j in G has every possible pair from ?_gi × ?_gj appearing in some row. The number of rows in such array is called its size. Given a weighted graph G, a mixed covering array on G with minimum size is called optimal. In this article, we give upper and lower bounds on the size of mixed covering arrays on graphs based on graph homomorphisms. We provide constructions for covering arrays on graphs based on basic graph operations. In particular, we construct optimal mixed covering arrays on trees, cycles and bipartite graphs; the constructed optimal objects have the additional property of being nearly point balanced. © 2007 Wiley Periodicals, Inc. J Combin Designs 15: 393–404, 2007     

New upper bounds on the minimum size of covering designs

Let D = {B₁, B₂,…, B_b} be a finite family of k-subsets (called blocks ) of a v-set X(v) = {1, 2,…, v} (with elements called points ). Then D is a (v, k, t) covering design or covering if every t-subset of X(v) is contained in at least one block of D. The number of blocks, b, is the size of the covering, and the minimum size of the covering is called the covering number , denoted C(v, k, t). This article is concerned with new constructions of coverings. The constructions improve many upper bounds on the covering number C(v, k, t) © 1998 John Wiley & Sons, Inc. J Combin Designs 6:21–41, 1998     

Covering arrays with mixed alphabet sizes

Covering arrays with mixed alphabet sizes, or simply mixed covering arrays, are natural generalizations of covering arrays that are motivated by applications in software and network testing. A (mixed) covering array A of type is a k × N array with the cells of row i filled with elements from ? and having the property that for every two rows i and j and every ordered pair of elements (e,f) ∈ ? × ?, there exists at least one column c, 1 ≤ c ≤ N, such that A_i,c = e and A_j,c = f. The (mixed) covering array number, denoted by , is the minimum N for which a covering array of type with N columns exists. In this paper, several constructions for mixed covering arrays are presented, and the mixed covering array numbers are determined for nearly all cases with k = 4 and for a number of cases with k = 5. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 413–432, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10059     

Some combinatorial constructions for optimal perfect deletion-correcting codes

There are two kinds of perfect t-deletion-correcting codes of length k over an alphabet of size v, those where the coordinates may be equal and those where all coordinates must be different. We call these two kinds of codes T*(k − t, k, v)-codes and T(k − t, k, v)-codes respectively. The cardinality of a T(k − t, k, v)-code is determined by its parameters, while T*(k − t, k, v)-codes do not necessarily have a fixed size. Let N(k − t, k, v) denote the maximum number of codewords in any T*(k − t, k, v)-code. A T*(k − t, k, v)-code with N(k − t, k, v) codewords is said to be optimal. In this paper, some combinatorial constructions for optimal T*(2, k, v)-codes are developed. Using these constructions, we are able to determine the values of N(2, 4, v) for all positive integers v. The values of N(2, 5, v) are also determined for almost all positive integers v, except for v = 13, 15, 19, 27 and 34.      

Incomplete perfect mendelsohn designs with block size 4 and one hole of size 7

Let v,k, and n be positive integers. An incomplete perfect Mendelsohn design, denoted by k-IPMD(v,n), is a triple (X, Y, ??) where X is a v-set (of points), Y is an n-subset of X, and ?? is a collection of cyclically ordered k-subsets of X (called blocks) such that every ordered pair (a, b) ∈ (X × X)?(Y × Y) appears t-apart in exactly one block of ?? and no ordered pair (a,b) ∈ Y × Y appears in any block of ?? for any t, where 1 ≤ t ≤ k ? 1. In this article, we obtain conclusive results regarding the existence of 4-IPMD(v,7) where the necessary conditions are v = 2 or 3(mod 4) and v ≥ 22. We also provide an application to the problem relating to coverings of PMDs with block size 4. © 1993 John Wiley & Sons, Inc.     

Combinatorial coverings from geometries over principal ideal rings

A t-(v, k, λ) covering is an incidence structure with v points, each block incident on exactly k points, such that every set of t distinct points is incident on at least λ blocks. By considering certain geometries over finite principal ideal rings, we construct infinite families of t-(v, k, λ) coverings having many interesting combinatorial properties. © 1999 John & Sons, Inc. J Combin Designs 7: 247–268, 1999     

New constructions for covering designs

A(v, k, t) covering design, or covering, is a family of k-subnets, called blocks, chosen from a v-set, such that each t-subnet is contained in at least one of the blocks. The number of blocks is the covering's size, and the minimum size of such a covering is denoted by C(v,k,t). This paper gives three new methods for constructing good coverings; a greedy algorithm similar to Conway and Sloane's algorithm for lexicographic codes [6], and two methods that synthesize new coverings from preexisting ones. Using these new methods, together with results in the literature, we build tables of upper bounds on C(v,k,t) for v ? 32, k ? 16, and t ? 8. © 1995 John Wiley & Sons, Inc.     

Optimum super-simple mixed covering arrays of type <Emphasis Type="Italic">a</Emphasis><Superscript>1</Superscript><Emphasis Type="Italic">b</Emphasis><Superscript><Emphasis Type="Italic">k</Emphasis>−1</Superscript>

A mixed covering array (MCA) of type (_v 1, v ₂,..., v _k ), denoted by MCA_λ (N; t, k, (v ₁, v ₂,..., v _k )), is an N × k array with entries in the i-th column from a set _{V i} of v _i symbols and has the property that each N × t sub-array covers all the t-tuples at least λ times, where 1 ≤ i ≤ k. An MCA _λ (N; t, k, (_v 1, v ₂,..., v _k )) is said to be super-simple, if each of its N × (t + 1) sub-arrays contains each (t + 1)-tuple at most once. Recently, it was proved by Tang, Yin and the author that an optimum super-simple MCA of type (a, b, b,..., b) is equivalent to a mixed detecting array (DTA) of type (a, b, b,..., b) with optimum size. Such DTAs can be used to generate test suites to identify and determine the interaction faults between the factors in a component-based system. In this paper, some combinatorial constructions of optimum super-simple MCAs of type (a, b, b,..., b) are provided. By employing these constructions, some optimum super-simple MCAs are then obtained. In particular, the spectrum across which optimum super-simple MCA₂(2b ²; 2, 4, (a, b, b, b))′s exist, is completely determined, where 2 ≤ a ≤ b.     

Incomplete perfect mendelsohn designs with block size 4 and holes of size 2 and 3

Let v, k, and n be positive integers. An incomplete perfect Mendelsohn design, denoted by k-IPMD(v, n), is a triple (X, Y, ??) where X is a v-set (of points), Y is an n-subset of X, and ?? is a collection of cyclically ordered k-subsets of X (called blocks) such that every ordered pair (a, b) ∈ (X × X)\(Y × Y) appears t-apart in exactly one block of ?? and no ordered pair (a,b) ∈ Y × Y appears in any block of ?? for any t, where 1 ≤ t ≤ k ? 1. In this article, the necessary conditions for the existence of a 4-IPMD(v, n), namely (v ? n) (v ? 3n ? 1) ≡ 0 (mod 4) and v ≥ 3n + 1, are shown to be sufficient for the case n = 3. For the case n = 2, these conditions are sufficient except for v = 7 and with the possible exception of v = 14,15,18,19,22,23,26,27,30. The latter result provides a useful application to the problem relating to the packing of perfect Mendelsohn designs with block size 4. © 1994 John Wiley & Sons, Inc.