Full Record

Author | Francetic, Nevena |

Title | Covering Arrays with Row Limit |

URL | http://hdl.handle.net/1807/34006 |

Publication Date | 2012 |

Date Available | 2012-01-01 00:00:00 |

Degree Level | doctoral |

University/Publisher | University of Toronto |

Abstract | 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. PhD |

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 | 2020-03-09 |

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…