Full Record

New Search | Similar Records

Title Covering Arrays with Row Limit
Publication Date
Date Available
Degree Level doctoral
University/Publisher University of Toronto

Covering arrays with row limit, CARLs, are a new family of combinatorial objects which we introduce as a generalization of group divisible designs and covering arrays. In the same manner as their predecessors, CARLs have a natural application as combinatorial models for interaction test suites. A CARL(N;t,k,v:w), is an N×k array with some empty cells. A component, which is represented by a column, takes values from a v-set called the alphabet. In each row, there are exactly w non-empty cells, that is the corresponding components have an assigned value from the alphabet. The parameter w is called the row limit. Moreover, any N×t subarray contains every of v^t distinct t-tuples of alphabet symbols at least once. This thesis is concerned with the bounds on the size and with the construction of CARLs when the row limit w(k) is a positive integer valued function of the number of columns, k. Here we give a lower bound, and probabilistic and algorithmic upper bounds for any CARL. Further, we find improvements on the upper bounds when w(k)ln(w(k)) = o(k) and when w(k) is a constant function. We also determine the asymptotic size of CARLs when w(k) = Θ(k) and when w(k) is constant. Next, we study constructions of CARLs. We provide two combinatorial constructions of CARLs, which we apply to construct families of CARLs with w(k)=ck, where c<1. Also, we construct optimal CARLs when t=2 and w=4, and prove that there exists a constant δ, such that for any v and k≥4, an optimal CARL(2,k,v:4) differs from the lower bound by at most δ rows, with some possible exceptions. Finally, we define a packing array with row limit, PARL(N;t,k,v:w), in the same way as a CARL(N;t,k,v:w) with the difference that any t-tuple is contained at most once in any N×t subarray. We find that when w(k) is a constant function, the results on the asymptotic size of CARLs imply the results on the asymptotic size of PARLs. Also, when t=2, we consider a transformation of optimal CARLs with row limit w=3 to optimal PARLs with w=3.


Subjects/Keywords group divisible designs; covering arrays; group divisible covering desings; graph covering problem; packing arrays; group divisible packing designs; 0405
Contributors Mendelsohn, Eric; Mathematics
Language en
Country of Publication ca
Record ID handle:1807/34006
Repository toronto-diss
Date Retrieved
Date Indexed 2020-03-09

Sample Search Hits | Sample Images

…32 u1 u2 us of type g1 g2 . . . gs GDCD group divisible covering design 27 GDP D group divisible packing design 32 us 1 u2 K − DGDD of type (n, hu 1 h2 . . . hs ) double group divisible design 17 K − HGDD of type (n, hu )…

…are incident to the pairs of 32 elements not contained in any block or a group of a GDCD Chapter 1 Introduction Covering arrays with row limit, CARLs for short, are a new family of combinatorial objects which we introduce as a generalization of group

…divisible designs and covering arrays, two well-known families of objects in combinatorial design theory. Group divisible designs, GDDs for short, were introduced as statistical experiment designs [17, 51]. On the other hand, covering arrays model…

…6, 2 : 4). We state the formal definitions of GDDs and covering arrays in Chapter 2 and of CARLs and P ARLs in Chapter 3. Here we introduce CARLs by an example. Then we discuss the applications and the characteristics of group divisible designs…

…family of combinatorial objects. In the array representation, these objects are called CARLs and their notation is consistent with the notation for covering arrays. On the other hand, in the set version, these objects are called group divisible covering

…divisible covering designs with block size four), we develop constructions of optimal CARLs with strength t = 2 and row limit w = 4. Since the strength is equal to two and the row limit is a constant, we construct group divisible covering designs with…

…considering pairwise covering, that is when strength t is 2, we can equivalently consider a CARL as a generalization of GDDs, which motivates the following definition of group divisible covering designs. Definition 3.3. A group divisible covering design, a…

…relation between a CARL and a covering version of a group divisible t-design. However, group divisible t-designs have not been much explored. To our knowledge there are only two papers which consider this generalization of GDDs [42, 43]. In this…