Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

Sorted by: relevance · author · university · dateNew search

Language: English

You searched for subject:(graph covering problem). Showing records 1 – 2 of 2 total matches.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters

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

Degree: 2012, 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.

PhD

Advisors/Committee Members: Mendelsohn, Eric, Mathematics.

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… 

Page 1 Page 2 Page 3 Page 4 Page 5 Page 6 Page 7

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

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

APA (6th 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 (16th Edition):

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

MLA Handbook (7th Edition):

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

Vancouver:

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

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 DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

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

APA (6th 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 (16th Edition):

Sheppard, Nicholas Paul. “Self-Reduction for Combinatorial Optimisation .” 2001. Thesis, University of Sydney. Accessed October 31, 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 (7th Edition):

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

Vancouver:

Sheppard NP. Self-Reduction for Combinatorial Optimisation . [Internet] [Thesis]. University of Sydney; 2001. [cited 2020 Oct 31]. 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

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

.