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

…interpreted as an edge covering problem in the graph theory. are contributing new results to the graph edge covering problem. As with any covering problem, two central questions in the study of CARLs are: what the minimum size of a covering is and how to…

covering arrays with row limit, CARLs, and related structures. We introduce the problem in all three equivalent forms which offer different tools and perspective to the study: array, set, and graph variation. Regarding the two central questions of minimum…

…dissertation, if the strength is two and the row limit is a constant, we study GDCDs; otherwise, we consider CARLs. The graph covering definition Finally, when t = 2, the problem of finding an optimal CARL or a GDCD can be formulated as a version of the graph

covering problem [1, 8]. A graph G is a pair (V (G), E(G)) where V (G) is the set of vertices of G, and E(G) is the set of edges of G. Let (V, G, B) be a GDCD with block size k. The set…

…families of GDDs with block size k ≥ 6 [14]. Covering arrays were first applied in the zero-error noisy channel communication problem [33] and in compressing inconsistent data [32]. With the rapid development of the software…

…Unlike GDDs which may exist only when the necessary conditions are satisfied, the existence problem of covering arrays is trivial; they always exist since for each t-tuple of elements, we can dedicate a row to cover it. However, determining the minimum…

…number of rows is a difficult problem [11]. There are many bounds on the size of a covering array, but for a given a set of parameters, the optimal size of a covering array is not known in general [11, 14]. A natural generalization of…

…size and construction of optimal objects, we define the cover number and the excess graph, two properties of CARLs. We also define the packing version of the problem, that is, packing arrays with row limit, P ARLs, and the related structures. We…