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

…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…