Advanced search options

Language: English ^{❌}

You searched for `+publisher:"University of Toronto" +contributor:("Mendelsohn, Eric")`

. One record found.

▼ Search Limiters

1. Francetic, Nevena. Covering Arrays with Row Limit.

Degree: 2012, University of Toronto

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

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

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Francetic, N. (2012). Covering Arrays with Row Limit. (Doctoral Dissertation). University of Toronto. Retrieved from http://hdl.handle.net/1807/34006

Chicago Manual of Style (16^{th} Edition):

Francetic, Nevena. “Covering Arrays with Row Limit.” 2012. Doctoral Dissertation, University of Toronto. Accessed October 27, 2020. http://hdl.handle.net/1807/34006.

MLA Handbook (7^{th} Edition):

Francetic, Nevena. “Covering Arrays with Row Limit.” 2012. Web. 27 Oct 2020.

Vancouver:

Francetic N. Covering Arrays with Row Limit. [Internet] [Doctoral dissertation]. University of Toronto; 2012. [cited 2020 Oct 27]. Available from: http://hdl.handle.net/1807/34006.

Council of Science Editors:

Francetic N. Covering Arrays with Row Limit. [Doctoral Dissertation]. University of Toronto; 2012. Available from: http://hdl.handle.net/1807/34006