Advanced search options

Sorted by: relevance · author · university · date | New search

You searched for `subject:(graph covering problem)`

.
Showing records 1 – 2 of
2 total matches.

▼ 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

…GDDs and *covering* arrays, CARLs can
be interpreted as an edge *covering* *problem* in the *graph*… …theory.
are contributing new results to the *graph* edge *covering* *problem*.
As with any *covering*… …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*… …*problem*, two central questions in the study of CARLs are: what
the minimum size of a *covering* is…

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 September 28, 2020. http://hdl.handle.net/1807/34006.

MLA Handbook (7^{th} Edition):

Francetic, Nevena. “Covering Arrays with Row Limit.” 2012. Web. 28 Sep 2020.

Vancouver:

Francetic N. Covering Arrays with Row Limit. [Internet] [Doctoral dissertation]. University of Toronto; 2012. [cited 2020 Sep 28]. 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

University of Sydney

2. Sheppard, Nicholas Paul. Self-Reduction for Combinatorial Optimisation .

Degree: 2001, University of Sydney

URL: http://hdl.handle.net/2123/797

This thesis presents and develops a theory of self-reduction. This process is used to map instances of combinatorial optimisation problems onto smaller, more easily solvable instances in such a way that a solution of the former can be readily re-constructed, without loss of information or quality, from a solution of the latter. Self-reduction rules are surveyed for the Graph Colouring Problem, the Maximum Clique Problem, the Steiner Problem in Graphs, the Bin Packing Problem and the Set Covering Problem. This thesis introduces the problem of determining the maximum sequence of self-reductions on a given structure, and shows how the theory of confluence can be adapted from term re-writing to solve this problem by identifying rule sets for which all maximal reduction sequences are equivalent. Such confluence results are given for a number of reduction rules on problems on discrete systems. In contrast, NP-hardness results are also presented for some reduction rules. A probabilistic analysis of self-reductions on graphs is performed, showing that the expected number of self-reductions on a graph tends to zero as the order of the graph tends to infinity. An empirical study is performed comparing the performance of self-reduction, graph decomposition and direct methods of solving the Graph Colouring and Set Covering Problems. The results show that self-reduction is a potentially valuable, but sometimes erratic, method of finding exact solutions to combinatorial problems.

Subjects/Keywords: combinatorial optmisation; self-reduction; confluence; decomposition; graph colouring; steiner problem; bin packing; set covering

Record Details Similar Records

❌

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

APA (6^{th} Edition):

Sheppard, N. P. (2001). Self-Reduction for Combinatorial Optimisation . (Thesis). University of Sydney. Retrieved from http://hdl.handle.net/2123/797

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

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

Sheppard, Nicholas Paul. “Self-Reduction for Combinatorial Optimisation .” 2001. Thesis, University of Sydney. Accessed September 28, 2020. http://hdl.handle.net/2123/797.

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^{th} Edition):

Sheppard, Nicholas Paul. “Self-Reduction for Combinatorial Optimisation .” 2001. Web. 28 Sep 2020.

Vancouver:

Sheppard NP. Self-Reduction for Combinatorial Optimisation . [Internet] [Thesis]. University of Sydney; 2001. [cited 2020 Sep 28]. Available from: http://hdl.handle.net/2123/797.

Note: this citation may be lacking information needed for this citation format:

Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Sheppard NP. Self-Reduction for Combinatorial Optimisation . [Thesis]. University of Sydney; 2001. Available from: http://hdl.handle.net/2123/797

Not specified: Masters Thesis or Doctoral Dissertation